two-sum

1. 两数之和

• https://leetcode.cn/problems/two-sum/description/

容易想到，可以从第一个数开始，计算需要的数字，然后查找是否有这个数字。

时间复杂度为 O(n^2),空间复杂度为 O(1)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int n = nums.size();
        for(int i = 0;i < n;++i){
            int need = target - nums[i];
            for(int j = i+1;j < n;++j){
                if(nums[j]==need){
                    return {i,j};
                }
            }
        }
        return {-1,-1};
    }
};

分析可知主要耗时在查找需要的数字上面，可以使用 hash 加速这个过程，hash 可以在 O(1)的时间里检验是否存在这个数字。

同时因为需要返回下标，所以需要使用 hashmap 存储这个过程。

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

        for (auto it : m) {
            auto o = m.find(target - it.first);
            if (o != m.end()) {
                return {it.second, o->second};
            }
        }

        return {-1, -1};
    }
};

但是这样还有一个问题，如果有重复的数就会出错,因为 hash 冲突了，如下：

[3,3]

所以这里有个小技巧，就是一边查询一边插入，这样如果有重复的就直接输出了，还能减少空间使用。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        const int n = nums.size();
        unordered_map<int, int> m;
        for (int i = 0; i < n; ++i) {
            auto o = m.find(target - nums[i]);
            if (o != m.end()) {
                return {i, o->second};
            }
            m[nums[i]] = i;
        }

        return {-1, -1};
    }
};