两数之和-力扣

看到这题首先想到的解法是两个for循环，进行暴力枚举即可，代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        for(int i = 0; i < nums.size() - 1; i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] == target){
                    v.push_back(i);
                    v.push_back(j);
                }
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 看了题解，返回类型是 vector<int>，没必要再单独创建一个v来一个一个push_back，直接返回{a,b}这样一个数组也是可以的。

另一种方法是使用哈希表来实现，使用一个map记录每个元素出现的下标，这样遍历到一个元素，只需向map查询是否存在 target - nums[i] 是否存在即可，从而减少了一个for循环，大大降低了时间复杂度。
代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            int key = target - nums[i];
            if(mp.find(key) != mp.end()){
                return {mp[key] , i };
            }else {
                mp[nums[i]] = i;
            }
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但第二种写法似乎更习惯于这样去写（对迭代器的使用）：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16