千问 LeetCode 18. 四数之和 Java实现

LeetCode 18. 四数之和的核心解法是排序 双指针时间复杂度为 O(n³)本质是三数之和的扩展固定前两个数再用双指针找后两个数。核心思路1. 排序便于使用双指针和去重2. 两层循环枚举前两个数 nums[i] 和 nums[j]3. 双指针在剩余区间用 left 和 right 找后两个数4. 去重每层都要跳过重复元素避免结果重复Java 完整实现class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger res new ArrayList();if (nums null || nums.length 4) return res;Arrays.sort(nums);int n nums.length;for (int i 0; i n - 3; i) {// 去重跳过相同的第一个数if (i 0 nums[i] nums[i - 1]) continue;// 剪枝当前最小的四个数之和已大于target后续不可能有解if ((long) nums[i] nums[i 1] nums[i 2] nums[i 3] target) break;// 剪枝当前数 最大的三个数仍小于target跳过当前iif ((long) nums[i] nums[n - 3] nums[n - 2] nums[n - 1] target) continue;for (int j i 1; j n - 2; j) {// 去重跳过相同的第二个数if (j i 1 nums[j] nums[j - 1]) continue;// 剪枝当前最小的四数之和已大于targetif ((long) nums[i] nums[j] nums[j 1] nums[j 2] target) break;// 剪枝当前两数 最大的两个数仍小于targetif ((long) nums[i] nums[j] nums[n - 2] nums[n - 1] target) continue;int left j 1, right n - 1;while (left right) {long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 去重跳过相同的第三个数和第四个数while (left right nums[left] nums[left 1]) left;while (left right nums[right] nums[right - 1]) right--;left;right--;} else if (sum target) {left;} else {right--;}}}}return res;}}关键细节- sum 用 long题目中 nums[i] 范围是 -10⁹ ~ 10⁹四个数相加可能超出 int 范围必须用 long 防止溢出- 去重条件 j i 1第二层去重判断的是 j i 1 而非 j 0因为 j 的合法起始位置是 i 1第一个 j 不应被跳过- 剪枝不能简单用 nums[i] target因为数组中可能有负数nums[i] target 不代表后续组合一定超 target必须用四数之和的上下界来判断- 去重在找到解之后left 和 right 的去重只在 sum target 时执行确保不遗漏合法组合复杂度项目 复杂度时间 O(n³)空间 O(log n)排序栈空间这道题的套路和三数之和完全一致掌握后可以推广到 N 数之和递归 双指针属于双指针系列的必刷经典题。要不要顺带看看 N 数之和的通用递归框架四数之和其实是它的特例掌握框架后能直接套。