1_两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

1
2
3
4


给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路：

方法一：

暴力法，从前向后i与j = i+1相加看看是不是 target。

方法二：

从头遍历一遍，查看target与nums[i]的差在不在hash_map里，如果是则返回结果。如果不是将当前这个数和这个数的索引值存到hash_map里。

因为如果与当前这个数匹配的另一个数如果存在肯定是traget-nums[i]，那么剩下的任务就是查找这个数。从头到尾遍历一遍就能保证将全部的数据都搜索到。时间复杂度当然就是O(n)了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

vector<int> twoSumHash(vector<int> nums,int target){
    vector<int> ans;
    unordered_map<int,int> map;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target-nums[i];
        unordered_map<int, int>::iterator it;
        it = map.find(complement);
        if (it != map.end()) {
            ans = {it->second,i};
        }else{
            map.insert(make_pair(nums[i], i));
        }
    }
    return  ans;
}