LeetCode-18-四数之和_给你一个长度为n的整数那么4和1个目标-CSDN博客

本文链接：https://blog.csdn.net/CodAlun/article/details/120743689

这篇博客讨论了如何解决寻找数组中四个整数，使得它们的和等于给定目标值的问题。通过排序和双指针技术，可以优化算法，减少循环次数，从而提高效率。博主分享了两种优化后的解决方案，分别是三层循环加双指针和两层循环加双指针的方法，这两种方法都在避免重复和优化循环上下了功夫，以达到更好的时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

来源：LeetCode.

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

示例 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 < = n u m s . l e n g t h < = 200$
$- 109 < = n u m s [i] < = 109$
$- 109 < = t a r g e t < = 109$

接下来看一下解题思路：

思路：排序 + 双指针：

这道题与三数之和类似，也可以用相同的思路来解决这道题
为了避免枚举到重复四元组，则需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素；
可以对数组进行排序，并且在循环过程中遵循以下两点：

每一种循环枚举到的下标必须大于上一重循环枚举到的下标；
同一重循环中，如果当前元素与上一个元素相同，则跳过当前元素；
因为数组已经被排序，因此可以使用双指针的方法去掉一重循环；
保持第三重循环不变，而将第四重循环变成一个从数组最右端开始向左移动的指针；
注意：还需要保持左指针一直在右指针的左侧（即满足 $\leq d$ ）

public static List<List<Integer>> fourSum1(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();

    if (nums == null || nums.length < 4) {
        return result;
    }
    // 排序
    Arrays.sort(nums);
    int len = nums.length;
    // 枚举第一个数字 a
    for (int i = 0; i < len; ++i) {
        // 需要和上一次枚举的数不同
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 枚举第二个数字 b
        for (int j = i + 1; j < len; ++j) {
            // 需要和上一次枚举的数不同
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            // 枚举第三个数字 c
            for (int k = j + 1; k < len; ++k) {
                // 需要和上一次枚举的数不同
                if (k > j + 1 && nums[k] == nums[k - 1]) {
                    continue;
                }
                // 右指针
                int m = len - 1;
                // 需要保证第三个数字 c 在第四个数字 d 的左侧
                while (m > k && nums[i] + nums[j] + nums[k] + nums[m] > target) {
                    --m;
                }
                // 第三个数字 c 和第四个数字 d 重合，随着 c 后续的增加，
                // 就不会满足 a+b+c+d=0 并且 c < d 的 c 了，可以退出循环。
                if (m == k) {
                    break;
                }
                if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    list.add(nums[m]);
                    result.add(list);
                }
            }
        }
    }
    return result;
}

然而，即使用双指针省去了一层for循环，但是效率仍然不高，还可以做一些优化；
使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数；
假设两重循环枚举到的前两个数分别位于下标 $i$ 和 $j$ ，其中 $i < j$ 。初始时，左右指针分别指向下标 $j + 1$ 和下标 $n - 1$ 。每次计算四个数的和，并进行如下操作：

如果和等于 $\textit{target}$ ，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数；
如果和小于 $\textit{target}$ ，则将左指针右移一位；
如果和大于 $\textit{target}$ ，则将右指针左移一位。

我们还可以做一些优化，避免一些多余的循环：

在确定第一个数之后，如果 $\textit{nums}[i]+\textit{nums}[i+1]+\textit{nums}[i+2]+\textit{nums}[i+3]>\textit{target}$ ，说明此时剩下的三个数无论取什么值，四数之和一定大于 $\textit{target}$ ，因此退出第一重循环；
在确定第一个数之后，如果 $\textit{nums}[i]+\textit{nums}[n-3]+\textit{nums}[n-2]+\textit{nums}[n-1]<\textit{target}$ ，说明此时剩下的三个数无论取什么值，四数之和一定小于 $\textit{target}$ ，因此第一重循环直接进入下一轮，枚举 $\textit{nums}[i+1]$ ；
在确定前两个数之后，如果 $\textit{nums}[i]+\textit{nums}[j]+\textit{nums}[j+1]+\textit{nums}[j+2]>\textit{target}$ ，说明此时剩下的两个数无论取什么值，四数之和一定大于 $\textit{target}$ ，因此退出第二重循环；
在确定前两个数之后，如果 $\textit{nums}[i]+\textit{nums}[j]+\textit{nums}[n-2]+\textit{nums}[n-1]<\textit{target}$ ，说明此时剩下的两个数无论取什么值，四数之和一定小于 $\textit{target}$ ，因此第二重循环直接进入下一轮，枚举 $\textit{nums}[j+1]$ ；

public static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();

    if (nums == null || nums.length < 4) {
        return result;
    }
    Arrays.sort(nums);
    int n = nums.length;
    // 枚举第一个数字 a
    for (int i = 0; i < n - 3; ++i) {
        // 需要和上一次枚举的数不同
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 此时剩下的三个数无论取什么值，四数之和一定大于 target，因此退出第一重循环；
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 此时剩下的三个数无论取什么值，四数之和一定小于 target，因此第一重循环直接进入下一轮，枚举 nums[i+1]；
        if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
            continue;
        }
        // 枚举第二个数字 b
        for (int j = i + 1; j < n - 2; ++j) {
            // 需要和上一次枚举的数不同
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }
            int left = j + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                // 如果和等于 target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数
                if (sum == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    ++left;
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    --right;
                } else if(sum < target){   // 如果和小于 target，则将左指针右移一位
                    ++left;
                } else {  // 如果和大于 target，则将右指针左移一位
                    --right;
                }
            }
        }
    }
    return result;
}

总结

时间复杂度： $O(n^3)$ ，其中 $n$ 是数组的长度。排序的时间复杂度是 $\log n)$ ，枚举四元组的时间复杂度是 $O(n^3)$ ，因此总时间复杂度为 $O(n^3+n\log n)=O(n^3)$ ；
空间复杂度： $O(\log n)$ ，其中 $n$ 是数组的长度。空间复杂度主要取决于排序额外使用的空间。使用了一个额外的数组存储了数组 $\textit{nums}$ 的副本并排序，空间复杂度为 $O (n)$ ；