Array + two points leetcode.18

题面

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.

给定无序数组，找到和为target的不重复的长度为4的子序列

样例

1. Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

2. Given array nums = [0， 0， 0， 0], and target = 0.
solution set is:
[
  [0, 0, 0, 0]  
]
note: This example need to think specially！

3. Given array nums = [-3， -3， -3， 2， 2， 2，0， 0， 0， 3， 3， 3], and target = 0.
solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
Note: How to deal with the duplicate quadruplets ?

思路（这里是4个数的和为target，我们之前不是做过3个数的吗？Refer this one 正好可以用上）

1. 升序排序（sort即可）

2. 不可避免地要遍历数组（i）

3. 借鉴leetcode-15中的三个数的和，我们如法炮制，搜索剩下的三个数（j = i+1, l=j+1, r = size()-1）；对参数有疑惑的话，看下面代码。

时间复杂度：O(n³)，暴力的话应该会超时，没试！

这题里面尤其要注意避免重复

源码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int len = nums.size();
        if(len < 4)
            return res;
        
        sort(nums.begin(), nums.end());
        for(int i=0; i<=len-4; i++)
        {
            while(i>0 && i<=len-4 && nums[i]==nums[i-1])
                i++;//消除i的重复
            for(int j=i+1; j<=len-3; j++)
            {
                while(j>i+1 && j<=len-3 && nums[j]==nums[j-1])
                    j++;//消除j的重复
                int l=j+1, r=len-1;
                while(l < r)
                {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum > target)
                        r--;
                    else if(sum < target)
                        l++;
                    else
                    {
                        res.push_back(vector<int> {nums[i], nums[j], nums[l], nums[r]});
                        while(l<r && nums[l]==nums[l+1]) l++;//消除l的重复
                        while(l<r && nums[r]==nums[r-1]) r--;//消除r的重复
                        l++; r--;
                    }
                }
            }
        }
        return res;
    }
};

如果对消除重复有疑问的童鞋，请留言， 或者自行把example 3 手推一遍就明白了。