Two Sum

LeetCode #1

Description:

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, and you may not use the same element twice.

Example:

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

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

Idea:

用hash table， 先过一遍，key是数组的值，value是index。然后在过一遍数组，找key=target-nums[i]存在不存在。注意：找到的key必学要在现在的index i之后，不然1. 重复， 2. 比如3+3=6，用了两遍现有的值。

Code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash_tb;
        for(int i=0; i<nums.size(); i++){
            hash_tb[nums[i]]=i;
        }

        vector<int> result;
        for(int i=0; i<nums.size(); i++){
            if(hash_tb.find(target-nums[i])!=hash_tb.end()&&hash_tb[target-nums[i]]>i ){
                // Don't forget this: &&hash_tb[target-nums[i]]>i
                result.push_back(i);
                result.push_back(hash_tb[target-nums[i]]);
                return result;
            }
        }

    }
};