双指针与滑动窗口中等1 种解法
#18四数之和
返回数组中所有和为 target 且互不重复的四元组。
#数组#排序#双指针
原题
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、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
解题主线
- 排序后固定前两个数，后两个数用相向双指针寻找。
- 所有加减法都提升为 long，避免 target 与多个 int 运算时溢出。
解法 1：双重枚举 + 双指针
固定 first、second 后，在右侧有序区间查找和为剩余目标的数对。
-
时间复杂度： O(n³)
-
空间复杂度： O(log n)，排序栈；不计结果
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// 排序后固定前两项，剩余区间用相向指针维持单调搜索。
// 固定项和命中数对都要跳过重复值，保证四元组唯一。
// 求和提升为 long，避免多个 int 相加或与 target 相减时溢出。
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int first = 0; first + 3 < n; first++) {
if (first > 0 && nums[first] == nums[first - 1]) continue;
for (int second = first + 1; second + 2 < n; second++) {
if (second > first + 1 && nums[second] == nums[second - 1]) continue;
long remaining = (long) target - nums[first] - nums[second];
int left = second + 1;
int right = n - 1;
while (left < right) {
long pair = (long) nums[left] + nums[right];
if (pair < remaining) {
left++;
} else if (pair > remaining) {
right--;
} else {
result.add(List.of(nums[first], nums[second], nums[left], nums[right]));
int leftValue = nums[left];
int rightValue = nums[right];
while (left < right && nums[left] == leftValue) left++;
while (left < right && nums[right] == rightValue) right--;
}
}
}
}
return result;
}
}边界与易错点
- 四层位置都必须正确去重。
- 依赖 target 符号的简单剪枝并不普适；应使用有序边界和或不剪枝。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q018_fourSum.java