nSum问题

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

思路：

暴力解法是双重循环暴力枚举，我们发现可以在第二层循环时，通过哈希表在O(1)的时间内找到target - nums[i]。

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 tmp = target - nums[i];
            if(mp.count(tmp)){
                return {mp[tmp], i};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};

时间空间复杂度为O(N)。

在讲三数之和，我们先改动一下两数之和，假设我们现在要求返回的不是下标，而是数字。我们就可以先通过排序，然后二分查找。可以假设只有且仅有一对儿元素可以凑出 target。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //排序
      sort(nums.begin(), nums.end());
      //左右指针
      int lo = 0, hi = nums.size() - 1;
      while(lo < hi){
        int sum = nums[lo] + nums[hi];
        if(sum < target){
          lo++;
        }else if(sum > target){
          hi--;
        }else{
          return {nums[lo], nums[hi]};
        }
      }
      return {};
    }
};

这样就可以解决这个问题，不过我们要继续魔改题目，把这个题目变得更泛化，更困难一点：

nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。

函数签名如下：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target);

比如说输入为 nums = [1,3,1,2,2,3], target = 4，那么算法返回的结果就是：[[1,3],[2,2]]。

对于修改后的问题，关键难点是现在可能有多个和为 target 的数对儿，还不能重复，比如上述例子中 [1,3] 和 [3,1] 就算重复，只能算一次。

首先，基本思路肯定还是排序加双指针：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target {
    // 先对数组排序
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 根据 sum 和 target 的比较，移动左右指针
        if      (sum < target) lo++;
        else if (sum > target) hi--;
        else {
            res.push_back({lo, hi});
            lo++; hi--;
        }
    }
    return res;
}

但是，这样实现会造成重复的结果，比如说 nums = [1,1,1,2,2,3,3], target = 4，得到的结果中 [1,3] 肯定会重复。

出问题的地方在于 sum == target 条件的 if 分支，当给 res 加入一次结果后，lo 和 hi 不应该改变 1 的同时，还应该跳过所有重复的元素：

所以代码如下；

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {
            while (lo < hi && nums[hi] == right) hi--;
        } else {
            res.push_back({left, right});
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}

这样，一个通用化的 twoSum 函数就写出来了，请确保你理解了该算法的逻辑，我们后面解决 3Sum 和 4Sum 的时候会复用这个函数。

这个函数的时间复杂度非常容易看出来，双指针操作的部分虽然有那么多 while 循环，但是时间复杂度还是 O(N)，而排序的时间复杂度是 O(NlogN)，所以这个函数的时间复杂度是 O(NlogN)。

15. 三数之和

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

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

示例：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

思路：

这样，我们再泛化一下题目，不要光和为 0 的三元组了，计算和为 target 的三元组吧，同上面的 twoSum 一样，也不允许重复的结果：

这里就相当于target = 0

这个问题怎么解决呢？很简单，穷举呗。现在我们想找和为 target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！

那么，确定了第一个数字之后，剩下的两个数字可以是什么呢？其实就是和为 target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int> > res;
      	int target = 0;
        //穷举第一个数
        for(int i = 0; i < n; i++){
            //对 target - nums[i] 计算 twoSum
            vector<vector<int> > tuples = twoSumTarget(nums, i + 1, target - nums[i]);
            //如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
            for(vector<int>& tuple : tuples){
                tuple.push_back(nums[i]);
                res.push_back(tuple);
            }
            //跳过第一个数字重复的情况
            while(i < n - 1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
    vector<vector<int> > twoSumTarget(vector<int>& nums, int start, int target){
        int lo = start, hi = nums.size() - 1;
        vector<vector<int> > res;
        while(lo < hi){
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if(sum < target){
                while(lo < hi && nums[lo] == left) lo++;
            }else if(sum > target){
                while(lo < hi && nums[hi] == right) hi--;
            }else{
                res.push_back({left, right});
                while(lo < hi && nums[lo] == left) lo++;
                while(lo < hi && nums[hi] == right) hi--;
            }
        }
        return res;
    }
};