16.最接近的三数之和

LeetCode LeetCode 数组 双指针 排序
发布时间 :
字数:2.3k 阅读 : 评论:
  1. 16.最接近的三数之和
    1. 16.1 题目
    2. 16.2 题解
      1. 方法一：暴力法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：双指针法
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 16.3 代码
    4. 16.4 运行结果

16.最接近的三数之和

16.1 题目

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

示例：

  • 示例 1：

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

  • 示例 2：

    • 输入：nums = [0,0,0], target = 1
    • 输出：0

提示：

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4

16.2 题解

方法一：暴力法

思路

用三层循环枚举所有可能的三元组，计算三数之和与目标值的差值，记录差值最小的和。

具体步骤：

  1. 遍历所有可能的三元组 (i, j, k)，其中 i < j < k。
  2. 计算每个三元组的和 currentSum = nums[i] + nums[j] + nums[k]。
  3. 比较 |currentSum - target| 与当前最小差值，更新最接近的和。

举例：对于 nums = [-1,2,1,-4], target = 1：

  • 三元组 (-1, 2, 1) 的和为 2，与目标差 |2-1| = 1
  • 三元组 (-1, 2, -4) 的和为 -3，与目标差 |-3-1| = 4
  • 三元组 (-1, 1, -4) 的和为 -4，与目标差 |-4-1| = 5
  • 三元组 (2, 1, -4) 的和为 -1，与目标差 |-1-1| = 2
  • 最接近的是 2，差值最小为 1。

注意：此方法时间复杂度高，不推荐使用。

复杂度分析

  • 时间复杂度：O(n^3)，三层循环。
  • 空间复杂度：O(1)，只使用常数额外变量。

代码

static int ThreeSumClosest1(int[] nums, int target)
{
    // 排序数组，以方便后续使用指针查找最接近的三数之和
    Array.Sort(nums);

    // 初始化最接近的三数之和，设置为整型最大值，以确保任何合法的三数之和都会比该值小
    int closestSum = int.MaxValue;

    // 遍历数组，固定第一个元素
    for (int i = 0; i < nums.Length - 2; i++)
    {
        // 使用两层循环固定第二个和第三个元素，寻找与目标值最接近的三数之和
        for (int j = i + 1; j < nums.Length - 1; j++)
        {
            for (int k = j + 1; k < nums.Length; k++)
            {
                // 计算当前三个数的和
                int currentSum = nums[i] + nums[j] + nums[k];

                // 判断当前的三数之和是否更接近目标值
                if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum))
                {
                    // 如果更接近，更新最接近的三数之和
                    closestSum = currentSum;
                }
            }
        }
    }

    // 返回最终找到的最接近目标值的三数之和
    return closestSum;
}

方法二：双指针法

思路

与三数之和思路类似。先排序，固定一个数，然后用双指针在右侧查找。根据当前三数之和与目标值的关系移动指针，记录最接近的和。

核心思想：排序后利用单调性，用双指针快速逼近目标值。

具体步骤：

  1. 对数组排序。
  2. 遍历数组，固定第一个数 nums[nowKey]。
  3. 用左右指针 leftKey 和 rightKey 在 nowKey 右侧查找：
    • 计算 tempSum = nums[nowKey] + nums[leftKey] + nums[rightKey]
    • 如果 tempSum == target，直接返回（已经最接近）
    • 如果 tempSum > target，rightKey--（减小和）
    • 如果 tempSum < target，leftKey++（增大和）
    • 每次更新最接近的和

举例：对于 nums = [-1,2,1,-4], target = 1，排序后为 [-4,-1,1,2]：

  • 固定 nowKey=0，nums[0]=-4：
    • left=1, right=3：-4 + (-1) + 2 = -3，差值 4，更新 closestSum=-3
    • -3 < 1，left++，left=2：-4 + 1 + 2 = -1，差值 2，更新 closestSum=-1
  • 固定 nowKey=1，nums[1]=-1：
    • left=2, right=3：-1 + 1 + 2 = 2，差值 1，更新 closestSum=2
  • 最终返回 2。

复杂度分析

  • 时间复杂度：O(n^2)，外层循环 O(n)，内层双指针 O(n)。
  • 空间复杂度：O(1)，只使用常数额外变量。

代码

// 方法二：双指针法
// 和15题思路类似 定位1个主键然后主键右侧双指针逐步逼近
static int ThreeSumClosest2(int[] nums, int target)
{
    // 若数组长度小于等于 3，只有唯一一组三元组，其和即为答案
    if (nums.Length <= 3)
    {
        return nums.Sum();
    }

    // 排序数组，以方便后续使用指针查找最接近的三数之和
    Array.Sort(nums);

    // 初始化最接近的三数之和，设置为整型最大值，以确保任何合法的三数之和都会比该值小
    int closestSum = int.MaxValue;

    int leftKey;
    int rightKey;

    // 遍历数组，固定第一个元素
    for (int nowKey = 0; nowKey < nums.Length - 2; nowKey++)
    {
        // 初始化左右指针
        leftKey = nowKey + 1;
        rightKey = nums.Length - 1;

        // 使用双指针在数组的剩余部分寻找与目标值最接近的三数之和
        while (leftKey < rightKey)
        {
            // 计算当前三个数的和
            int tempSum = nums[nowKey] + nums[leftKey] + nums[rightKey];

            // 判断当前的三数之和是否更接近目标值
            if (DistanceFromTarget(tempSum, target) < DistanceFromTarget(closestSum, target))
            {
                // 如果更接近，更新最接近的三数之和
                closestSum = tempSum;
            }

            // 判断是否找到完全匹配的三数之和，若是，则直接返回
            if (tempSum == target)
            {
                return tempSum;
            }
            else if (tempSum > target)
            {
                // 如果当前三数之和大于目标值，右指针左移
                rightKey--;
            }
            else
            {
                // 如果当前三数之和小于目标值，左指针右移
                leftKey++;
            }
        }
    }

    // 返回最终找到的最接近目标值的三数之和
    return closestSum;
}

// 辅助函数：计算当前和目标值的距离
static int DistanceFromTarget(int nowSum, int target)
{
    return Math.Abs(nowSum - target);
}

16.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 1：
        // 输入：nums = [-1,2,1,-4], target = 1
        // 输出：2
        // 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

        // 示例 2：
        // 输入：nums = [0,0,0], target = 1
        // 输出：0

        // 提示：
        // 3 <= nums.length <= 1000
        // -1000 <= nums[i] <= 1000
        // -104 <= target <= 104

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { -1, 2, 1, -4 };
        int target1 = 1;
        int result1 = ThreeSumClosest1(nums1, target1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = ThreeSumClosest2(nums1, target1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 0, 0, 0 };
        int target2 = 1;
        int result2 = ThreeSumClosest1(nums2, target2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = ThreeSumClosest2(nums2, target2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：暴力法
    // 三种循环暴力求解 很慢
    static int ThreeSumClosest1(int[] nums, int target)
    {
        // 排序数组，以方便后续使用指针查找最接近的三数之和
        Array.Sort(nums);

        // 初始化最接近的三数之和，设置为整型最大值，以确保任何合法的三数之和都会比该值小
        int closestSum = int.MaxValue;

        // 遍历数组，固定第一个元素
        for (int i = 0; i < nums.Length - 2; i++)
        {
            // 使用两层循环固定第二个和第三个元素，寻找与目标值最接近的三数之和
            for (int j = i + 1; j < nums.Length - 1; j++)
            {
                for (int k = j + 1; k < nums.Length; k++)
                {
                    // 计算当前三个数的和
                    int currentSum = nums[i] + nums[j] + nums[k];

                    // 判断当前的三数之和是否更接近目标值
                    if (Math.Abs(target - currentSum) < Math.Abs(target - closestSum))
                    {
                        // 如果更接近，更新最接近的三数之和
                        closestSum = currentSum;
                    }
                }
            }
        }

        // 返回最终找到的最接近目标值的三数之和
        return closestSum;
    }


    // 方法二：双指针法
    // 和15题思路类似 定位1个主键然后主键右侧双指针逐步逼近
    static int ThreeSumClosest2(int[] nums, int target)
    {
        // 若数组长度小于等于 3，只有唯一一组三元组，其和即为答案
        if (nums.Length <= 3)
        {
            return nums.Sum();
        }

        // 排序数组，以方便后续使用指针查找最接近的三数之和
        Array.Sort(nums);

        // 初始化最接近的三数之和，设置为整型最大值，以确保任何合法的三数之和都会比该值小
        int closestSum = int.MaxValue;

        int leftKey;
        int rightKey;

        // 遍历数组，固定第一个元素
        for (int nowKey = 0; nowKey < nums.Length - 2; nowKey++)
        {
            // 初始化左右指针
            leftKey = nowKey + 1;
            rightKey = nums.Length - 1;

            // 使用双指针在数组的剩余部分寻找与目标值最接近的三数之和
            while (leftKey < rightKey)
            {
                // 计算当前三个数的和
                int tempSum = nums[nowKey] + nums[leftKey] + nums[rightKey];

                // 判断当前的三数之和是否更接近目标值
                if (DistanceFromTarget(tempSum, target) < DistanceFromTarget(closestSum, target))
                {
                    // 如果更接近，更新最接近的三数之和
                    closestSum = tempSum;
                }

                // 判断是否找到完全匹配的三数之和，若是，则直接返回
                if (tempSum == target)
                {
                    return tempSum;
                }
                else if (tempSum > target)
                {
                    // 如果当前三数之和大于目标值，右指针左移
                    rightKey--;
                }
                else
                {
                    // 如果当前三数之和小于目标值，左指针右移
                    leftKey++;
                }
            }
        }

        // 返回最终找到的最接近目标值的三数之和
        return closestSum;
    }

    // 辅助函数：计算当前和目标值的距离
    static int DistanceFromTarget(int nowSum, int target)
    {
        return Math.Abs(nowSum - target);
    }

    #endregion
}

16.4 运行结果

示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：0
示例2 方法2 输出：0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏