【LeetCode刷题日记】18.四数之和

北极的代码

发布于 2026-04-22 14:12:51

710

前言：

前面我们刚刷完了三数之和，这里我们继续学习四数之和，看着是比三数之和更难一点，但其实代码逻辑都是一样的，让我们看看吧。

摘要：

本文介绍了LeetCode 18题"四数之和"的解题思路与Java实现。该题要求在给定数组中找到所有不重复的四元组，使其和等于目标值。解题采用双指针法，在排序后的数组基础上，通过两层循环固定前两个数，再用双指针寻找后两个数，同时进行剪枝优化和去重处理。时间复杂度为O(n³)，与三数之和类似但多一层循环。文章详细解析了代码逻辑，包括排序、双重循环、双指针移动、剪枝条件和去重操作，并指出其可扩展性（五数、六数之和等）。最后提供了完整的Java代码示例和测试用例。

题目背景：LeetCode18

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

题目答案：

import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 结果集
        for (int k = 0; k < nums.length; k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break;	// 此处的break可以等价于return result;
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;	// 注意是break到上一级for循环，如果直接return result;会有遗漏
                }
                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}

题目解析：

四数之和，和15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和的基础上再套一层for循环。但是有一些细节需要注意例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成if (nums[i] > 0 && nums[i] > target) break;就可以了。 15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。那么一样的道理，五数之和、六数之和等等都采用这种解法。

代码逻辑：

首先我们先排序数组，然后创建一个结果集合，用来存储结果。

然后我们最外层的循环，来遍历第一个元素，负责选出四个数中的第一个

关于第一层去重：

if (nums[k] > target && nums[k] >= 0) {
                break;	// 此处的break可以等价于return result;
            }

第一层的去重，是为了提前结束，相当于三数之和的第一个条件，如果大于零直接返回。在这里，我们的条件是要求nums[k]>target,并且nums[k]>=0，因为数组是按顺序排的，然后呢这个nums[k]还是四个数中的第一个，所以后面的三个数一定大于nums[k],况且nums[k]已经大于target了，所以再寻找后面的三个元素已经是多余的了，完全不存在的结果，所以直接break。

然后接下来就是：

 // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;

这个跟三数之和的去重逻辑一模一样

如果当前第一个数 == 上一个第一个数，直接跳过！

直接 continue 跳过
不会重复生成答案 ✅

然后就是第二级枝剪：

  for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;	// 注意是break到上一级for循环，如果直接return result;会有遗漏
                }

这个目的是为了寻找第二个元素

固定前两个数之后，发现这俩加起来已经太大了，后面就不用找了，直接跳出这层循环。

一步步拆开讲

k：第一个数
i：第二个数

这时候前两个数已经定下来了，后面还有两个数（left、right），而且数组是排好序的。

所以：后面的数 只会 ≥ 当前的数，只会越来越大。

然后就是对第二个元素进行去重：

 // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }

跟三数之和去重第二个元素一样

再者之后，我们去找第三个和第四个数：

 int left = i + 1;
                int right = nums.length - 1;

找到这四个数字，我们计算总和sum，之后进行比较：

 while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }

关于这里的去重思路和三数之和的去重一样，进行移动去重。

while 去重 → 跳过相同数字

最后 left++ /right-- → 移动到新位置，继续找下一组解

少了最后一步，指针不动，会死循环！

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！