Leetcode题目链接：18. 四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n

• a、b、c 和 d 互不相同

• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

题目示例

示例一

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

示例二

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示

1 <= nums.length <= 200
-10的9次 <= nums[i] <= 10的9次
-10的9次 <= target <= 10的9次

解题思路

双指针遍历去重

• 本题是在三数之和的基础上加入一层外层循环实现

• 定义二维结果数组vector<vector<int>> result用于记录满足条件的四元组

• 使用C++自带的sort函数对给出的数组nums进行升序排序（为后续判断提供便利）

• 一层for循环遍历nums数组，开始对四元组进行查找、比较、去重、加入结果集

  • 判断当前元素num[k]是否已经大于等于0并且大于target值（这里的target值并不固定，所以需要两个判定条件）

  • 使用nums[k] == nums[k - 1]进行判断，如果条件满足，则上一次就已经把相同的满足条件的四元组加入了结果集，跳过本次循环

  • 执行内层for循环，进行二级查找、比较、去重、加入结果集

    • 二级剪枝同上述操作

    • 定义left指针，初始指向当前位置i的下一个位置，向后不断移动

    • 定义right指针，初始指向数组的最后一个元素的位置，向前不断移动

    • 执行while循环，循环条件为 left < right，即当前数组中还有未被验证是否符合的四元组

      • 计算res值，res = nums[k] + nums[i] + nums[left] + nums[right]

      • 判断res值的大小情况

        • res > target 当前四元组的计算结果过大，将right位置向前移动，指向更小的元素，使结果从正数向target趋近

        • res < target 当前四元组的计算结果过小，将left位置向后移动，指向更大的元素，使结果从负数向target趋近

        • res == target 满足条件，将其加入到result结果集中

          • 这里还需要使用两个while循环继续缩减left和right的范围，过滤掉与当前满足条件的四元组相同结果的情况（对特殊情况进行去重操作）

          • 每完成一个加入结果集的操作，都要进行双指针收缩的 left++ 和 right-- 的操作

• 返回结果集result

我的答案

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int k = 0; k < nums.size(); k++) {
            //剪枝并去重
            if(nums[k] > target && nums[k] >= 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            for(int i = k + 1; i < nums.size(); i++) {
                int current = nums[k] + nums[i];
                //二级剪枝
                if(current > target && current >= 0) break;
                //二级去重
                if(i > k + 1 && nums[i] == nums[i - 1]) continue;
                int left = i + 1;
                int right = nums.size() - 1;
                while(left < right) {
                    long res = (long)nums[k] + nums[i] + nums[left] + nums[right];
                    if(res > target) right--;     
                    else if(res < target) left++;
                    else {
                        result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
                        while(left < right && nums[right] == nums[right - 1]) right--;
                        while(left < right && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
};

提交结果