山羊面经

外观

四数之和

约 3474 字大约 12 分钟

排序中等百度

2024-12-24

⭐ 题目日期：

百度 - 2024/12/6

🌳 题目描述：

四数之和

给定一个数组和一个目标值，要求找出并返回所有满足条件的四元组 [nums[a], nums[b], nums[c], nums[d]]，使得：

  • 四个数之和等于 target，即 nums[a] + nums[b] + nums[c] + nums[d] == target。
  • 下标 a, b, c, d 互不相同。
  • 结果中不能包含重复的四元组。
示例 1：
输入：nums = [-2, -1, 0, 0, 1, 2], target = 0
输出：[[-2, -1, 1, 2], [-2, 0, 0, 2]]

🕵🏽‍♂️ 面试评估：

这道题主要考察候选者是否能够通过理解排序与双指针的核心思想，在一个有序数组中高效地寻找所有满足条件的四元组，同时考察候选者是否能够结合剪枝优化（提前判断最小/最大和与目标值的关系）来提高效率以及正确处理去重逻辑以避免重复解。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

题目是四数之和，那么我们可以逐步从一数之和到四数之和来分解问题：

  • 一数之和

    如果只要求数组中某个数等于 target，那就是直接判断数组中的元素是否等于目标值 target，直接遍历数组即可，这里没有特别的优化空间。

  • 两数之和

    给定一个数组，找到两个数的和等于 target：使用哈希表来记录已经遍历过的数字，比直接双层循环效率更高，之前写过相应的题解：两数之和题解

  • 三数之和

    要求三个数的和等于 target：如果使用三层循环来遍历，复杂度会是 O(n³)。我们可以进行优化，先排序数组，再固定第一个数，通过固定第一个数，将问题转换为在剩余部分找到两个数的和为目标值减去固定数的差值，例如，当数组为 [1, 3, 5, 7]，target = 11时，如果我们固定 1，那么接下来只需要在剩余的 [3, 5, 7]部分中找到两个数的和为 11 - 1 = 10，这样便得到简化。接下来采用双指针解法，left 指针从固定的第一个数之后的位置开始，即 left = i + 1。这时 left 指针指向的是除了固定数之外这个数组最小的数，right 指针指向数组的最后一个位置，即 right = nums.length - 1，这个数组最大的数。随后算出当前三个数相加的和 sum，如果 sum 大于所要求的 target，那么便减小这个和，right 向左移动；如果和小于所要求的 target，那么便增大这个和，left 向右移动；直至找到 sum = target。总的时间复杂度为 O(n²)。

  • 四数之和

    在三数之和的基础上引入第四个数，要求四个数的和等于 target：继续先排序数组，这个时候我们可以固定前两个数，使用双指针寻找剩余两个数，这种方法可以先进行剪枝，大大提高了效率。

这道题是要求寻找等于目标值的组合，为了避免暴力枚举所有可能的组合，我们可以利用双指针的特点：通过左右指针从两端向中间逼近，从而缩小问题的范围。

  1. 首先进行排序

    那么为什么要先排序呢？以四数之和为例，排序是解决问题的基础步骤。排序的目的在于让数组有序，方便后续通过指针调整范围并快速判断是否满足条件。以双指针法为核心，我们利用排序后的数组特性：

    • 当和 sum 小于目标值 target 时，左指针向右移动以增大和；当和大于目标值 target 时，右指针向左移动以减小和。
    • 且可以提前 剪枝，减少无意义的遍历和计算，从而提高效率：
      • 如果最小的数和已经大于 target，说明后续的数值更大，不可能找到满足条件的组合，因此直接退出当前循环。
      • 如果当前数与最大的三个数之和小于 target，说明当前数太小，不可能满足条件，那么直接跳过当前数。

  2. 固定前两个数，使用双指针查找剩余两个数

    接下来我们通过两个循环依次固定前两个数 nums[i] 和 nums[j]，然后在剩余的部分使用双指针查找剩下的两个数。

    循环规则：

    1. 外层循环控制第一个数 nums[i]，保证后面至少还剩三个数可以用，这里需要进行适当的去重和剪枝提高效率

      • 去重：
        • 第一个数 nums[i] 去重：如果 nums[i] == nums[i-1]，跳过本轮循环
      • 剪枝：
        • 如果 nums[i] 和接下来的三个最小数之和已经大于 target，则当前及后续的 i 都不可能满足条件，直接退出
        • 如果 nums[i] 和数组中最大的三个数之和小于 target，则当前 i 太小，跳过这个 i

    2. 内层循环控制第二个数 nums[j]，保证后面至少还剩两个数可以用，j 一定要比 i 大，即 j = i + 1，这里需要进行适当的去重和剪枝提高效率

      • 去重：
        • 第二个数 nums[j] 去重：如果 nums[j] == nums[j-1]，跳过本轮循环
      • 剪枝：
        • 如果当前组合的最小和大于 target，直接退出
        • 如果当前组合的最大和小于 target，跳过这个 j

    3. 使用双指针 left 和 right 在 j + 1 到数组末尾之间查找剩余两个数

  3. 双指针查找：寻找满足条件的四元组

    对于每一对固定的 nums[i] 和 nums[j]，我们定义两个指针：

    • left 指向当前区间的最左侧元素，从 j + 1 开始向右搜索
    • right 指向当前区间的最右侧元素，从数组末尾 n - 1 开始向左搜索

    我们计算四数之和 sum，并根据其与目标值 target 的关系，移动指针：

    1. 若 sum == target：找到一个四元组，将其加入结果集
      • 指针这里也需要去重，当找到满足条件的四元组后，left++ 和 right-- 时需要注意跳过重复的数值
    2. 若 sum < target：说明当前和太小，左指针右移以增大和
    3. 若 sum > target：说明当前和太大，右指针左移以减小和

以案例所示，图解如下： img

💻代码(Java、Python、C++)：

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

    // 如果数组为空或者数组长度小于 4,不可能满足四元组
    if (nums == null || nums.length < 4) {
        return result;
    }

    // 排序
    Arrays.sort(nums);

    int n = nums.length;

    // 遍历数组,最外层循环,固定第一个数,保证后面至少还剩三个数可以用
    for (int i = 0; i < n - 3; i++) {

        // 如果当前数与前一个数相同,跳过以避免重复
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        // 如果 nums[i] 和接下来的三个最小数之和已经大于 target,则当前及后续的 i 都不可能满足条件,直接退出
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }

        // 如果 nums[i] 和数组中最大的三个数之和小于 target，则当前 i 太小，跳过这个 i
        if ((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;
            }

            // 如果当前组合的最小和大于 target,直接退出
            if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }

            // 如果当前组合的最大和小于 target,跳过这个 j
            if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }

            // 双指针查找,确定第三个和第四个数, left 从 j + 1 开始向右搜索, right 从数组末尾 n - 1 开始向左搜索
            int left = j + 1;
            int right = n - 1;

            // 计算当前四元组的和 sum,并与目标值 target 进行比较
            while (left < right) {
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                // 找到与 target 相等的组合,加入结果集
                if (sum == target) {
                    result.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) { // 如果 sum < target,说明当前和太小,左指针右移以增大和
                    left++;
                } else { // 如果 sum > target,说明当前和太大,右指针左移以减小和
                    right--;
                }
            }
        }
    }

    return result;
}

🚵🏻复杂度分析：

  • 时间复杂度：O(n³)，n 为数组的长度。其中，排序的时间复杂度是 O(n log n)，外层是两重循环，所以时间复杂度为 O(n²)，而内层双指针的时间复杂度在最坏情况下是 O(n)，因此整体复杂度是 O(n³)。
  • 空间复杂度：O(n)，n 是满足条件的四元组的数量。

🔬在线评测(Online Judge):

题目链接