18. 4Sum

题目描述：给定一个有n个整数的数组S和目标值target，找到其中所有由四个数a、b、c、d组成，使得a + b + c + d = target 的四元组。如：

given array S = [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]
]

分析：与 3sum 的思路一样，先排序再左右夹逼，由于多一层循环复杂度O(n^3)。或者用 hashmap 先缓存两个数的和，这也可用于3sum， 最终复杂度O(n^3)。

方法一：先排序再左右夹逼，时间复杂度O(n^3)，空间O(1)。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector< vector<int> > ans;
        if (nums.size() < 4) return ans;
        
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 3; i ++)
        {
            for (int j = i + 1; j < nums.size() - 2; j ++)
            {
                int l = j + 1, r = nums.size() - 1;
                while(l < r)
                {
                    if (nums[i] + nums[j] + nums[l] + nums[r] < target)
                        l ++;
                    else if (nums[i] + nums[j] + nums[l] + nums[r] > target)
                        r --;
                    else
                    {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        l ++;
                        r --;
                    }
                }
            }
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());          //erase函数删除两迭代器之间的元素，unique返回的是重排后第一个多余元素的位置
        return ans;
    }
};

方法二：先用 hashmap 缓存两个数的和，平均O(n^2 )，最坏O(n^4 )，空间复杂度O(n^2)。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector< vector<int> > ans;
        if (nums.size() < 4) return ans;
        
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<pair<int, int> > > mp;           //两数和为键，这两数下标对为值
        for (int i = 0; i < nums.size(); i ++)
            for (int j = i + 1; j < nums.size(); j ++)
                mp[nums[i] + nums[j]].push_back(pair<int, int>(i, j));
        
        for (int i = 0; i < nums.size(); i ++)
        {
            for (int j = i + 1; j < nums.size(); j ++)
            {
                int gap = target - nums[i] - nums[j];
                if (mp.find(gap) == mp.end())
                    continue;
                
                auto vec = mp[gap];
                for (int k = 0; k < vec.size(); k++)
                {
                    if (i <= vec[k].second)       //有重叠，因为存入map时pair中小下标在前，大下标在后。i < j， vec[k].first < vec[k].second。改为 (j >= vec[k].first) 也可通过。保证a != c && a != d && b != c && b != d
                        continue;
                    
                    ans.push_back({nums[ vec[k].first ], nums[ vec[k].second ], nums[i], nums[j]});             //a≤b≤c≤d
                }
            }
        }
        sort(ans.begin(), ans.end());     
        ans.erase(unique(ans.begin(), ans.end()), ans.end());          //去重，不能包含重复的四元组
        return ans;
    }
};