当前位置：首页 > article >正文

leetcode-16. 最接近的三数之和

article 2025/2/24 8:22:36

要解决这个问题，我们需要在给定的整数数组 nums 中找到三个整数，使它们的和与目标值 target 最接近，并返回这个和。假定每组输入只存在恰好一个解。

这是 三数之和最接近（3Sum Closest） 的问题，类似于经典的 三数之和（3Sum） 问题。我们可以采用高效的 排序加双指针法 来解决该问题。以下将详细介绍该方法的步骤、算法实现以及相关代码示例。

1. 问题描述与示例

1.1 问题描述

给定一个长度为 n 的整数数组 nums 和一个目标值 target，请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

1.2 示例

示例 1:

输入: nums = [-1, 2, 1, -4], target = 1
输出: 2
解释: 与目标值 1 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2:

输入: nums = [0, 0, 0], target = 1
输出: 0
解释: 与目标值 1 最接近的和是 0 (0 + 0 + 0 = 0)。

1.3 约束条件

数组 nums 的长度 n 满足 3 <= n <= 10^3（假设范围类似于 LeetCode）。
元素值的范围通常是 -10^4 <= nums[i] <= 10^4。
假定每组输入只存在恰好一个解。

2. 解题思路

要高效地找到三个数使其和最接近目标值 target，我们可以采用如下步骤：

排序数组： 首先对数组 nums 进行排序。这有助于后续使用双指针法，并且便于避免重复和优化搜索过程。
遍历数组，固定第一个元素： 使用一个循环遍历数组，将当前元素作为三元组的第一个元素。
使用双指针查找剩余两个元素： 对于每个固定的第一个元素，使用两个指针分别指向其后面的首尾位置，寻找两个数的和尽可能接近 target - nums[i]。
更新最接近的和： 通过比较当前三数之和与目标值的差，更新记录中最接近的和。

2.1 为什么使用排序加双指针法？

排序的好处：
- 有序性： 有序数组使得双指针能够高效移动，减少不必要的计算。
- 剪枝优化： 可以通过比较当前和与目标值的关系来决定指针移动的方向，从而提高效率。
双指针法的优势：
- 时间效率： 双指针法在已经排序的数组上能够在线性时间内完成查找，避免了使用三重循环带来的 $O(n^3)$ 的时间复杂度。
- 空间效率： 只需要常数级别的额外空间，保持空间复杂度为 $O (1)$ 。

2.2 步骤详解

步骤 1：排序数组

首先，对数组 nums 进行排序。这将有助于后续使用双指针法来高效查找三数之和。

步骤 2：遍历数组，固定第一个元素

使用一个循环 i 遍历数组中的每个元素，将 nums[i] 作为三元组的第一个元素。为了避免重复计算，我们可以跳过与前一个元素相同的元素。

步骤 3：使用双指针查找剩余两个元素

对于每个固定的 nums[i]：

初始化左指针 left = i + 1，右指针 right = n - 1。
计算当前三数之和 current_sum = nums[i] + nums[left] + nums[right]。
如果 current_sum 等于 target，直接返回 current_sum，因为这是最接近的情况。
否则，根据 current_sum 与 target 的比较关系，决定移动左指针或右指针：
- 如果 current_sum < target，则移动左指针以增大和。
- 如果 current_sum > target，则移动右指针以减小和。
在过程中，持续更新最接近的和 closest_sum。

步骤 4：记录最接近的和

通过不断比较当前三数之和与目标值的差异，更新记录中最接近的和。

2.3 时间和空间复杂度

时间复杂度： $O(n^2)$
- 排序的时间复杂度为 $\log n)$ 。
- 外层循环遍历 n 个元素，内层双指针遍历的总时间复杂度为 $O(n^2)$ 。
空间复杂度： $O (1)$ （不考虑输入和输出所需的空间）
- 只使用了常数级别的额外空间。

3. 算法实现

以下是使用 Python 和 Java 实现该算法的代码示例。

3.1 Python 实现

from typing import List

def three_sum_closest(nums: List[int], target: int) -> int:
    nums.sort()  # 步骤1：排序
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]  # 初始化最接近的和

    for i in range(n - 2):
        # 步骤2：避免重复的第一个元素（可选，在本问题中不影响结果，但优化可减少不必要的计算）
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            # 如果当前和更接近目标值，更新 closest_sum
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                left += 1  # 需要更大的和，移动左指针
            elif current_sum > target:
                right -= 1  # 需要更小的和，移动右指针
            else:
                # 当前和等于目标值，直接返回
                return current_sum

    return closest_sum

# 测试案例
if __name__ == "__main__":
    test_cases = [
        ([-1, 2, 1, -4], 1, 2),
        ([0, 0, 0], 1, 0),
        ([1, 1, 1, 0], -100, 2),
        ([1, 2, 5, 10, 11], 12, 13),
        ([-3, -2, -5, 3, -4], -1, -2),
    ]

    for nums, target, expected in test_cases:
        result = three_sum_closest(nums, target)
        print(f"输入: nums = {nums}, target = {target}")
        print(f"输出: {result} {'✅' if result == expected else '❌ (期望: '+str(expected)+')'}\n")

输出:

输入: nums = [-1, 2, 1, -4], target = 1
输出: 2 ✅

输入: nums = [0, 0, 0], target = 1
输出: 0 ✅

输入: nums = [1, 1, 1, 0], target = -100
输出: 2 ✅

输入: nums = [1, 2, 5, 10, 11], target = 12
输出: 13 ✅

输入: nums = [-3, -2, -5, 3, -4], target = -1
输出: -2 ✅

3.2 Java 实现

import java.util.Arrays;

public class ThreeSumClosestSolution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);  // 步骤1：排序
        int n = nums.length;
        // 初始化 closest_sum 为前三个数的和
        int closest_sum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {
            // 步骤2：避免重复的第一个元素（可选）
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int current_sum = nums[i] + nums[left] + nums[right];

                // 如果当前和更接近目标值，更新 closest_sum
                if (Math.abs(current_sum - target) < Math.abs(closest_sum - target)) {
                    closest_sum = current_sum;
                }

                if (current_sum < target) {
                    left++;  // 需要更大的和，移动左指针
                }
                else if (current_sum > target) {
                    right--; // 需要更小的和，移动右指针
                }
                else {
                    // 当前和等于目标值，直接返回
                    return current_sum;
                }
            }
        }

        return closest_sum;
    }

    // 测试方法
    public static void main(String[] args) {
        ThreeSumClosestSolution solution = new ThreeSumClosestSolution();
        int[][] testNums = {
            {-1, 2, 1, -4},
            {0, 0, 0},
            {1, 1, 1, 0},
            {1, 2, 5, 10, 11},
            {-3, -2, -5, 3, -4}
        };
        int[] testTargets = {1, 1, -100, 12, -1};
        int[] expected = {2, 0, 2, 13, -2};

        for (int i = 0; i < testNums.length; i++) {
            int result = solution.threeSumClosest(testNums[i], testTargets[i]);
            System.out.println("输入: nums = " + Arrays.toString(testNums[i]) + ", target = " + testTargets[i]);
            System.out.println("输出: " + result + (result == expected[i] ? " ✅" : " ❌ (期望: " + expected[i] + ")") + "\n");
        }
    }
}

输出:

输入: nums = [-1, 2, 1, -4], target = 1
输出: 2 ✅

输入: nums = [0, 0, 0], target = 1
输出: 0 ✅

输入: nums = [1, 1, 1, 0], target = -100
输出: 2 ✅

输入: nums = [1, 2, 5, 10, 11], target = 12
输出: 13 ✅

输入: nums = [-3, -2, -5, 3, -4], target = -1
输出: -2 ✅

4. 代码解析

4.1 步骤详解

步骤1：排序数组

nums.sort()

Arrays.sort(nums);

作用： 对数组进行排序，使得后续使用双指针时可以高效地移动指针来寻找合适的组合。
示例：
- 输入 [-1, 2, 1, -4] 排序后为 [-4, -1, 1, 2]。

步骤2：遍历数组，固定第一个元素

for i in range(n - 2):
    # 可选的跳过重复元素
    if i > 0 and nums[i] == nums[i - 1]:
        continue

for (int i = 0; i < n - 2; i++) {
    // 可选的跳过重复元素
    if (i > 0 && nums[i] == nums[i - 1]) continue;
}

作用： 遍历数组，将当前元素 nums[i] 作为三元组的第一个元素。
跳过重复元素（可选）： 以减少不必要的计算，但在本问题中由于只需要最接近的和，不影响结果，主要用于优化速度。

步骤3：使用双指针查找剩余两个元素

left = i + 1
right = n - 1

while left < right:
    current_sum = nums[i] + nums[left] + nums[right]

    # 更新最接近的和
    if abs(current_sum - target) < abs(closest_sum - target):
        closest_sum = current_sum

    if current_sum < target:
        left += 1
    elif current_sum > target:
        right -= 1
    else:
        return current_sum  # 精确匹配

int left = i + 1;
int right = n - 1;

while (left < right) {
    int current_sum = nums[i] + nums[left] + nums[right];

    // 更新最接近的和
    if (Math.abs(current_sum - target) < Math.abs(closest_sum - target)) {
        closest_sum = current_sum;
    }

    if (current_sum < target) {
        left++;
    }
    else if (current_sum > target) {
        right--;
    }
    else {
        return current_sum; // 精确匹配
    }
}

作用： 使用双指针 left 和 right 来寻找两个数，使得 nums[i] + nums[left] + nums[right] 最接近 target。
逻辑：
- 计算当前和 current_sum。
- 比较差值： 若当前和 current_sum 与 target 的差值小于之前记录的 closest_sum 与 target 的差值，则更新 closest_sum。
- 移动指针：
  - 如果 current_sum < target，说明需要更大的和，移动左指针 left 以增大和。
  - 如果 current_sum > target，说明需要更小的和，移动右指针 right 以减小和。
  - 如果 current_sum == target，则已找到最接近的和，直接返回。