LeetCode题目之腾讯精选练习（50题）：最接近的三数之和

绝地灬酷狼 2024-04-17 21:19 18阅读 0赞

# 题目 #

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

**示例**:

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

## 算法实现 ##

public static int ThreeSumClosest(int[] nums, int target)
    {
        
        int cha = int.MaxValue;
        int t = 0;
        Array.Sort(nums);
        int length = nums.Length;
        int first, last, sum;
        for (int i = 0; i < length - 2; )
        {
        
            first = i + 1;
            last = length - 1;
            do
            {
        
                if (first >= last) break;
                sum = nums[first] + nums[i] + nums[last];
                if (Math.Abs(target - sum) < cha)
                {
        
                    t = sum;
                    cha = Math.Abs(sum - target);
                }
                if (sum <= target)
                {
        
                    while (first < last && nums[first] == nums[++first]) ;
                }
                else
                {
        
                    while (first < last && nums[last] == nums[--last]) ;
                }
            } while (first < last);
            while (i + 1 < nums.Length && nums[i] == nums[++i]) ;
        }
        return t;
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 132 ms, 在所有 C\# 提交中击败了100.00%的用户  
**内存消耗** : 23.7 MB, 在所有 C\# 提交中击败了7.41%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

对之前三数之和稍加改进即可，即目标值由0改为任意值。

## 官方解答 ##

更为简洁，清楚。

public static int ThreeSumClosest2(int[] nums, int target)
    {
        
        Array.Sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        int start, end, sum;
        for (int i = 0; i < nums.Length - 2; i++)
        {
        
            start = i + 1;
            end = nums.Length - 1;
            while (start < end)
            {
        
                sum = nums[start] + nums[end] + nums[i];
                if (Math.Abs(target - sum) < Math.Abs(target - ans))
                    ans = sum;
                if (sum > target)
                    end--;
                else if (sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }

![在这里插入图片描述][2019090113300078.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/149d697789344faf99fd10256369a8b3.png
[2019090113300078.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/93bfaa963b364f38aa9e11cdc59fa9ef.png