16.最接近的三数之和

LeetCode LeetCode 数组排序双指针

发布时间 : 2000-01-10 00:01

字数:1.8k 阅读 :

评论:

16.最接近的三数之和

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 题解

暴力法

// 方法一：暴力法
// 三种循环暴力求解 很慢
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);
}

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