Two Sum

Posted on | In , , |

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

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

Analysis

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> umap; // another num, cur index;
        vector<int> vec(2);
        for (int i=0; i< nums.size(); ++i) {
            if (umap.count(nums[i])) {
                vec[0] = umap[nums[i]];
                vec[1] = i;
                return vec;
            } else {
                umap[target - nums[i]] = i;
            }
        }
        return vec;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        h = {}
        for index, item in enumerate(nums):
            if target - item not in h:
                h[item] = index
            else:
                return [index, h[target-item]]