当前位置：首页 > article >正文

18. 四数之和【力扣】——两层循环后的双指针法

article 2025/1/30 22:33:36

四数之和

给你一个由 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
你可以按任意顺序返回答案。

示例 1：

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

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

二数之和：一左一右两个指针
三数之和：一左一右两个指针，外面套一个循环
四数之和：一左一右两个指针，外面套一个循环，然后最外面再套一个循环

#include <vector>
#include <algorithm>
class Solution {
public:
    // 函数 fourSum 用于在给定的整数数组 nums 中找出所有不重复的四元组，使得它们的和等于目标值 target
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
        // 用于存储最终满足条件的四元组
        vector<vector<int>> result;
        if(nums.size()<4) return result;
        // 对输入数组进行排序，方便后续使用双指针法和去重操作
        sort(nums.begin(), nums.end());

        // 第一层循环，遍历数组作为四元组的第一个数
        for (int i = 0; i <= nums.size()-4; i++) {
            // 剪枝操作：当当前元素大于目标值且为非负数时，由于数组已排序，后续元素只会更大，不可能再找到满足条件的四元组，直接跳出循环
            if (nums[i] > target && nums[i] >= 0) {
                break;
            }
            // 去重操作：如果当前元素与前一个元素相同，则跳过当前循环，避免结果中出现重复的四元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 第二层循环，遍历数组作为四元组的第二个数
            for (int j = i + 1; j <= nums.size()-3; j++) {
                // 剪枝操作：当当前两个元素之和大于目标值且为非负数时，后续元素更大，无法找到满足条件的四元组，跳出循环
                if (nums[j] + nums[i] > target && nums[i] + nums[j] >= 0) {
                    break;
                }
                // 去重操作：如果当前元素与前一个元素相同，则跳过当前循环，避免结果中出现重复的四元组
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                // 双指针法，初始化左指针为 j + 1，右指针为数组末尾
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right) {
                    // 计算四个元素的和，使用 long 类型避免可能的整数溢出
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        // 如果和大于目标值，将右指针左移，以减小和
                        right--;
                    } else if (sum < target) {
                        // 如果和小于目标值，将左指针右移，以增大和
                        left++;
                    } else {
                        // 如果和等于目标值，将这四个元素组成的四元组添加到结果中
                        result.push_back(vector<int>{nums[i], nums[j], 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;
    }
};