Difficulty: Medium

这两道题其实是一个类型，都是TwoSum的变种。只要在外部循环里嵌套进TwoSum就好了。

SumTwo 总结

我们首先总结一下TwoSum的两种方法的优劣。两种方法：一种就是(对于有序元素)用双指针，对于重复元素可以快速跳过。另一种就是用hashmap(不要求有序)记录出现过的元素。它们都是线性复杂度。

我们分两种情况考虑：

情况一：只求一个解

如果天生有序，显然前一种方法更好(Two Sum II)，因为可能跳过元素加速，当然两种方法都是线性复杂度。如果无序，前一方法还要先排序，那么后一种方法就更好(TwoSum)。

如果要求的是输出结果在原数组中的位置，前一种方法可备份原数组，最后从原数组里查找。后一种方法使用unordered_map可直接记录(在数字可以重复的时候，返回的是原数组中的任一一个含有此数字的位置)。这对复杂度都不会有影响。

使用hashmap的时候，我们既可以渐进地向set里添加元素，每加一个元素之前都先找找set里有没有满足要求的另一半。我们也可以使用map(multiset)来记录每个元素出现的次数，然后依次对map中的元素找另一半。

情况二：要求所有解

这时候就必须去重。前一种方法有序输出，自带去重。后一种方法就要用RB-tree(vector不可被hash，所以不可以用hashmap)这反而会带来logn的复杂度。

对于无序输入，两种方法复杂度上无本质区别。但前一种方法可跳过重复元素，这在某些情况下会有优势(3Sum)。这时候如果要返回在原数组中的位置，因为数字可以重复，建立映射就比较麻烦了。

对于有序输入，显然前一种方法复杂度更低。

总结

总之，只有在无序且只求一解的情况下，采用hashmap有优势。

注

在使用双指针时，外层循环会有一个while(i<nums.size()-2)的逻辑，但一定要注意size_t与int做减法时可能会溢出。

3Sum Solution 1:

这道题要求的是所有解，一开始我没想清楚，想通过set来去重，但最后超时了。

class Solution {
  public:
    set < vector < int >> res;

  void sum2(vector < int > & nums, int i) {
    int target = -nums[i];
    unordered_set < int > s;
    for (int j = i + 1; j < nums.size(); j++) {
      if (s.count(target - nums[j])) {
        int a = nums[i];
        int b = nums[j];
        int c = target - nums[j];
        int m = min(min(a, b), c);
        int M = max(max(a, b), c);
        res.insert({
          m,
          -m - M,
          M
        });
      }
      s.insert(nums[j]);
    }
  }

  vector < vector < int >> threeSum(vector < int > & nums) {
    if (nums.size() < 3)
      return {};
    int i = 0;
    while (i < nums.size() - 2) {
      sum2(nums, i);
      i++;
      while (i < nums.size() - 2 && nums[i] == nums[i - 1]) i++;
    }
    return vector < vector < int >> (res.begin(), res.end());
  }
};

3Sum *Solution 2:

如前文所说，这就属于输入无序，求所有解的情况，应该先排序，再使用双指针。

class Solution {
  public:
    vector < vector < int >> res;
  vector < vector < int >> threeSum(vector < int > & nums) {
    sort(nums.begin(), nums.end());
    int i = 0;
    while (i < ((int) nums.size()) - 2) { ///
      if (nums[i] > 0) return res;
      check(nums, i);
      i++;
      while (i < nums.size() - 2 && nums[i] == nums[i - 1]) i++;
    }
    return res;
  }
  void check(vector < int > & nums, int i) {
    int target = -nums[i];
    int j = i + 1;
    int k = nums.size() - 1;
    while (j < k) {
      int sum = nums[j] + nums[k];
      if (sum > target) {
        k--;
        while (j < k && nums[k] == nums[k + 1]) k--;
        if (nums[k] < 0) return;
      } else if (sum < target) {
        j++;
        while (j < k && nums[j] == nums[j - 1]) j++;
      } else {
        res.push_back({
          nums[i],
          nums[j],
          nums[k]
        });
        k--;
        while (j < k && nums[k] == nums[k + 1]) k--;
      }
    }
  }
};

其实双指针如何保证不重不漏是需要仔细想一想的，这是通过每次i和j的起始位置来保证的。

4Sum Solution:

有了3Sum的基础，4Sum就一样做就行了。

class Solution {
  public:
    vector < vector < int >> res;
  vector < vector < int >> fourSum(vector < int > & nums, int target) {
    sort(nums.begin(), nums.end()); //i每次都是重复序列的第一个
    int i = 0;
    while (i < ((int) nums.size()) - 3) {
      int j = i + 1; //j每次都是从重复序列的第二个开始(如果有的话)
      while (j < ((int) nums.size()) - 2) {
        TwoSum(nums, target, i, j);
        j++;
        while (nums[j] == nums[j - 1] && j < nums.size() - 2) j++;
      }
      i++;
      while (nums[i] == nums[i - 1] && i < nums.size() - 2) i++;
    }
    return res;
  }
  void TwoSum(vector < int > & nums, int target, int i, int j) {
    int k = j + 1, l = nums.size() - 1;
    target = target - nums[i] - nums[j];
    while (k < l) {
      int sum = nums[k] + nums[l];
      if (sum < target) {
        k++;
        while (nums[k] == nums[k - 1] && k < l) k++;
      } else if (sum > target) {
        l--;
        while (nums[l] == nums[l + 1] && k < l) l--;
      } else {
        res.push_back({
          nums[i],
          nums[j],
          nums[k],
          nums[l]
        });
        k++;
        while (nums[k] == nums[k - 1] && k < l) k++;
        l--;
        while (nums[l] == nums[l + 1] && k < l) l--;
      }
    }
  }
};