Two Sum

题目：Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路：

就是使用hash表，for循环，如果target-num[i]是否存在，存在就直接输出结果。

然后再判断num[i]是否在hash表中。不存在就存入。

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //使用hash表
        vector<int>  last;
        map<int,int> hash_table;
        
        for(int i=0;i<nums.size();i++){
            if(hash_table.count(target-nums[i])==1){
                //查看减去的差值是否存在，因为题目说不会出现两个答案，所以只会等于1
                int n=hash_table[target-nums[i]];
                last.push_back(n+1);
                last.push_back(i+1);
                break;
            }
            if(hash_table.count(nums[i])==0){
                hash_table.insert(pair<int,int>(nums[i],i));//没有重复就输入到map中
                //1,1,2  在后面自然能够对第二个i进行处理
            }
            //如果判断target-nums[i]的if分支在后面，很容易遇到一个问题，
            //第一个进去3，target是6，刚刚进去3，然后6-3也在hash_table里面
            //直接退出
        }
        return last;
    }
};