leetcode: 几个数之和系列

两数之和

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

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

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

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> res;
        if (len < 3)
            return res;
        sort(nums.begin(), nums.end());
        for(int i=0;i<len-2;i++) {
            if(nums[i]>0) break; // 由于是已排序数组，所以后面的肯定都是正数了
            if(i>0 && nums[i]==nums[i-1]) // i-1已经算过一次了
                continue;
            int l=i+1;
            int r=len-1;
            while(l<r) {
                int sum = nums[i]+nums[l]+nums[r]; // 固定一个数，转化为两数之和
                if(sum == 0) {
                    res.push_back(vector({nums[i], nums[l], nums[r]}));
                    while(l<r && nums[l] == nums[l+1]) // 多走几步
                        l++;
                    while(l<r && nums[r] == nums[r-1])
                        r--;  
                    l++;
                    r--;
                } else if(sum > 0)
                    r--;
                else
                    l++;    
            }
        }
        return res;
    }
};

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        if(len < 3)
            return target;
        sort(nums.begin(), nums.end());
        int m=nums[0]+nums[1]+nums[2]; // 给一个初始值
        for(int i=0;i<len-2;i++) { // 另外有两个数，要减2
            int l=i+1;
            int r=len-1;
            while(l<r) {
                int sum = nums[i]+nums[l]+nums[r]; // 固定一个数i
                if(abs(sum-target)<abs(m-target))
                    m = sum;
                else if(sum>target)
                    r--;
                else if(sum<target)
                    l++;
                else
                    return target;
            }
        }
        return m;
    }
};

思考与总结

两个数之和在考虑时间复杂度时，需要一次遍历时把结果算出来，所以考虑使用hash表查询的方式，遍历的时候同时保存，以时间来换取空间。
三个数求和时，其实可以考虑成两个数求和的普遍情况，两个数求和是三个数求和的特例，所以思路是一样的，难点在于去重，这里使用排序后更好去重，同时利用双指针双边递进快速找到目标值。
最接近这个题，其实和三者之和那个题差不太多，找到最小值时再替换掉最小值，如果最小值为0了，就直接可以退出了。
这三个题的难度依次递增，重点难点在于，hash_map使用、双指针、排序去重等思路，把这些思路作为知识点，多加巩固练习，用得多就自然会了，不用的东西，总有一天会忘记的。