每日一道 LeetCode (53):最接近的三數(shù)之和

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：最接近的三數(shù)之和

難度：「中等」

題目來源：https://leetcode-cn.com/problems/3sum-closest/

給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target。找出 nums 中的三個(gè)整數(shù)，使得它們的和與 target 最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。

示例：

輸入：nums =?[-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2)?。

提示：

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

解題思路

這個(gè)題的解法和昨天的那個(gè)「三數(shù)之和」解題思路完全一致，唯一的區(qū)別就是這道題需要多一個(gè)全局變量，用于記錄每次計(jì)算時(shí)的差值的絕對(duì)值，最后返回一個(gè)最小的差值絕對(duì)值即可。

整體思路沒啥好說的，有不理解的可以翻翻前面的文章。

public?class?Solution?{
????public?int?threeSumClosest(int[]?nums,?int?target)?{
????????Arrays.sort(nums);
????????int?n?=?nums.length;
????????int?best?=?10000000;
????????//?外層循環(huán)?a
????????for?(int?a?=?0;?a?????????????//?保證和上一次循環(huán)的元素不相等
????????????if?(a?>?0?&&?nums[a]?==?nums[a?-?1])?{
????????????????continue;
????????????}
????????????int?b?=?a?+?1,?c?=?n?-?1;
????????????while?(b?????????????????int?sum?=?nums[a]?+?nums[b]?+?nums[c];
????????????????//?如果和為?target?直接返回答案
????????????????if?(sum?==?target)?{
????????????????????return?target;
????????????????}
????????????????//?根據(jù)差值的絕對(duì)值來更新答案
????????????????if?(Math.abs(sum?-?target)?????????????????????best?=?sum;
????????????????}
????????????????if?(sum?>?target)?{
????????????????????//?如果和大于?target，移動(dòng)?c?對(duì)應(yīng)的指針
????????????????????int?c0?=?c?-?1;
????????????????????//?移動(dòng)到下一個(gè)不相等的元素
????????????????????while?(b?????????????????????????--c0;
????????????????????}
????????????????????c?=?c0;
????????????????}?else?{
????????????????????//?如果和小于?target，移動(dòng)?b?對(duì)應(yīng)的指針
????????????????????int?j0?=?b?+?1;
????????????????????//?移動(dòng)到下一個(gè)不相等的元素
????????????????????while?(j0?????????????????????????++j0;
????????????????????}
????????????????????b?=?j0;
????????????????}
????????????}
????????}
????????return?best;
????}
}