1

Welcome to the leet wiki!

1. Two Sum

Problem Statement

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Because nums[0] + nums[1] == 9, we return [0, 1].

Constraints:

• 2 <= nums.length <= 105

• 109 <= nums[i] <= 109

• 109 <= target <= 109

• Only one valid answer exists.

Approach

For every element in nums check if target - nums , i.e. its complimentary number exists. To speed up the process use an unordered hash map.

Algorithm

def twoSums( nums[1...N], target):
    result[]
    dict <--- {}         # (num, position)
    for i from 1 to N:
        got <--- dict[ target - nums[i]) #position of compliment
        if got is the end of array, ie, if compliment does not exists:
            add (nums[i], position) to dict
        else:
            result <--- [got,i]  # position of num and compliment
            return result
    return result