18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

---

本题问一个数组中哪四个数加起来的和等于target，相当于LeetCode 3Sum的升级版，但是方法和3Sum是一样的，先枚举前两个数，对于后两个数，用首尾指针来求和。 一开始我的代码完全按照LeetCode 3Sum来写，先求最大最小值，然后用桶来hash，最后三层循环，代码如下：

class Solution {
public:
    vector<vector<int> > fourSum(vector<int>& nums, int target)
    {
        int min_v = INT_MAX, max_v = INT_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < min_v)
                min_v = nums[i];
            if (nums[i] > max_v)
                max_v = nums[i];
        }
        vector<int> hash(max_v – min_v + 1, 0);
        for (int i = 0; i < nums.size(); ++i) {
            ++hash[nums[i] – min_v];
        }
        vector<vector<int> > ans;
        for (int i = 0; i < hash.size(); ++i) {
            if (hash[i] == 0)
                continue;
            –hash[i];
            for (int j = i; j < hash.size(); ++j) {
                if (hash[j] == 0)
                    continue;
                –hash[j];
                int u = j, v = hash.size() – 1;
                while (u <= v) {
                    while (u <= v && hash[u] == 0)
                        ++u;
                    if (u > v)
                        break;
                    –hash[u];
                    while (u <= v && hash[v] == 0)
                        –v;
                    if (u > v) {
                        ++hash[u];
                        break;
                    }
                    –hash[v];
                    int sum = i + j + u + v + 4 * min_v;
                    ++hash[u];
                    ++hash[v];
                    if (sum == target) {
                        ans.push_back({ i + min_v, j + min_v, u + min_v, v + min_v });
                        ++u;
                        –v;
                    }
                    else if (sum < target)
                        ++u;
                    else
                        –v;
                }
                ++hash[j];
            }
            ++hash[i];
        }
        return ans;
    }
};

但是本代码提交TLE，看了一下，最后一个样例中，最小值有-236727523之小，最大值有91277418之大，导致hash数组太大了，从而无效的空for循环太多，最终TLE。
后来改用排序代替hash，需要注意为了防止重复结果，对四个数都要有去重的操作。代码如下：

class Solution {
public:
    vector<vector<int> > fourSum(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int> > ans;
        int n = nums.size();
        for (int i = 0; i < n – 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue; // 防止nums[i]重复
            for (int j = i + 1; j < n – 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue; // 防止nums[j]重复
                int u = j + 1, v = n – 1;
                while (u < v) {
                    int sum = nums[i] + nums[j] + nums[u] + nums[v];
                    if (sum == target) {
                        ans.push_back({ nums[i], nums[j], nums[u], nums[v] });
                        int k = u + 1;
                        while (k < v && nums[k] == nums[u])
                            ++k; // 防止nums[u]重复
                        u = k;
                        k = v – 1;
                        while (k > u && nums[k] == nums[v])
                            –k; // 防止nums[v]重复
                        v = k;
                    }
                    else if (sum < target)
                        ++u;
                    else
                        –v;
                }
            }
        }
        return ans;
    }
};

本代码提交AC，用时39MS。
还有一种思路是，先对数组中两数之和Hash，然后枚举两个两数之和，转换为类似Two Sum的方法，时间复杂度为$O(n^2)$。