题目内容

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

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

示例

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [], target = 0
输出：[]

提示

0 <= nums.length <= 200
$-10^9$ <= nums[i] <=$10^9$
$-10^9$ <= target <= $10^9$

题解

本题在思路上与上题类似，是一个排序+双指针的做法。

首先，还是要强调一下，我们如果要使用双指针，一定保证有序，因此排序这个步骤不可省略。

在保证有序的前提下，我们进行如下的思考：

1、因为双指针，所以一定会固定2个数，然后用2个指针寻找满足条件的答案。

2、因此至少需要两重循环，假设固定nums[i]和nums[j]，然后使用k和u来寻找满足条件的答案。

3、这里有一个小的剪枝，即在搜索的过程中，不管是固定的两个数还是用指针寻找的两个数，只要前后两个数一致时，就可以跳过。（因为有序，因此相同的数一定挨着，因此我们只需要保证前后两个数不同，就能够视为枚举了不同的情况）

4、类似三数之和，这里规定，i<j<k<u。

具体做法：

1、固定两个数，原则上k指针从j+1开始往右走，u指针从nums.size()-1处往左走。

2、首先在nums[i] + nums[j] + nums[k] + nums[u] ≥ target 且 u>k 的情况下，让u—。

3、在上述条件满足的前提条件下，再判断nums[i] + nums[j] + nums[k] + nums[u] == target 与u > k 是否满足即可。

4、如果满足，则加入答案中，不满足则继续寻找。

代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //首先还是排个序，然后固定两个值之后，用双指针求剩下两个值
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        for(int i = 0;i < nums.size(); i++){
            if(i && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1;j < nums.size(); j++){
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                for(int k = j + 1,u = nums.size() -1; k < u; k++){
                    if(k > j + 1 && nums[k] == nums[k - 1] ) continue;
                    while(u > k && nums[i] + nums[j] + nums[k] + nums[u] > target) u--;
                    if (nums[i] + nums[j] + nums[k] + nums[u] == target && u > k){
                        res.push_back({nums[i],nums[j],nums[k],nums[u]});
                    }
                }
            }
        }
        return res;
    }
};