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 <= 109
https://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;}
};