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

1.8 双指针专题：四数之和

news 来源：原创 2025/8/21 5:39:17

1.题目链接

18. 四数之和 - 力扣（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你可以按任意顺序返回答案。示例 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]] 提示： * 1 <= nums.length <= 200 * -109 <= nums[i] <= 109 * -109 <= target <= 109https://leetcode.cn/problems/4sum/

2.题目描述

给你⼀个由 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]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

3.算法思路

这段代码通过 排序 + 双指针法 解决了四数之和问题，核心思想是将四数之和转化为两数之和问题。以下是具体设计思路：

1. 排序预处理

首先对数组进行排序，目的有两点：

去重：排序后相同元素会相邻，方便后续跳过重复值。

双指针优化：有序数组可以通过双指针快速缩小搜索范围。

2. 分层固定 + 双指针搜索

外层循环固定前两个数：用 i 和 j 分别遍历第一个和第二个数。

剪枝：i 的范围是 [0, n-3)，j 的范围是 [i+1, n-2)，确保后续至少有两个数可选。

内层双指针搜索后两个数：用 left 和 right 在剩余区间 [j+1, n-1] 内寻找满足条件的组合。

计算 remain = target - nums[i] - nums[j]，转化为两数之和问题。

双指针根据当前和与 remain 的大小关系移动，缩小搜索范围：

sum > remain → right--（需要更小的值）。

sum < remain → left++（需要更大的值）。

sum == remain → 记录结果并去重。

3. 去重策略

外层循环去重：跳过 i 和 j 的重复值，避免重复解。
while (i < n - 3 && nums[i] == nums[i - 1]) i++;  // i去重
while (j < n - 2 && nums[j] == nums[j - 1]) j++;  // j去重
内层双指针去重：找到解后跳过 left 和 right 的重复值。
while (left < right && nums[left] == nums[left - 1]) left++;   // left去重
while (left < right && nums[right] == nums[right + 1]) right--; // right去重

**双指针算法与暴力枚举法对比表**
对比维度	双指针法（优化后）	暴力枚举法
时间复杂度	O(n³)（两层循环+双指针遍历）	O(n⁴)（四层循环遍历所有组合）
空间复杂度	O(1)（除结果存储外无额外空间）	O(1)
去重实现	通过排序和指针跳跃自动去重，逻辑清晰	需额外哈希表去重，实现复杂
适用场景	处理大规模数据（如 n=1000）	仅适用于极小规模数据（如 n=10）
剪枝优化	通过排序提前终止无效搜索（如剩余数过大/过小）	无优化，遍历所有可能组合

4.关键优化点

双指针替代两层循环：将后两数的遍历从 O(n²) 优化为 O(n)。

去重剪枝：通过排序和指针跳跃避免重复解，减少无效计算。

提前终止：在有序数组中，若当前最小和已大于目标值，可直接跳出循环。

5.总结

该算法通过 排序预处理 和 双指针法，将四数之和问题的时间复杂度从暴力法的 O(n⁴) 优化到 O(n³)，同时结合去重策略保证了结果的唯一性。相较暴力法，它在处理大规模数据时效率显著提升。

4.代码实现

class Solution 
{
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> arr;int length = nums.size();for (int i = 0; i < length - 3;) {for (int j = i + 1; j < length - 2;) {// 转化为：两数之和等于remain 问题long long remain =(long long)target - nums[i] - nums[j],sum = 0;int left = j + 1, right = length - 1;while (left < right) {sum = nums[left] + nums[right];if (sum > remain) right--;else if (sum <remain) left++;else {arr.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;// [left,right]去重while (left < right && nums[left] == nums[left - 1]) left++;while (left < right && nums[right] == nums[right + 1]) right--;}}j++;// j 去重while(j < length && nums[j] == nums[j - 1]) j++;}i++;// i 去重while(i < length && nums[i] == nums[i - 1]) i++;}return arr;}
};

1.题目链接

2.题目描述

3.算法思路

4.代码实现

相关文章：