Go 刷 leetcode｜大廠面試必備變形題

今天為大家講解 LeetCode 第 16 題，順藤摸瓜，接著昨天的三數(shù)之和 leetcode｜面試常客雙指針?biāo)惴}?

今天為大家分享這道變形題：最接近的三數(shù)之和。類似的題目一起講有利于學(xué)習(xí)鞏固，一起奧利給！

題目描述

給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標(biāo)值 target。找出 nums 中的三個整數(shù)，使得它們的和與 target 最接近。返回這三個數(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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/3sum-closest 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

了解昨天三數(shù)之和的話，這道題應(yīng)該也會有思路，同樣適用雙指針解法。

此題的算法思路如下：

1. 對數(shù)組進(jìn)行排序（排序是必須的，否則無法判斷及指針移動）。
2. 初始化返回結(jié)果 ans 為 nums[0] + nums[1] + nums[2]（初始化為Int的最大值也行，反正都是用于判斷跟新）
3. 遍歷排序后數(shù)組，并計算當(dāng)前指向三數(shù)的 sum = nums[i] + nums[l] + nums[r] ：
• 若 abs(target-sum) < ?abs(target-ans) （abs 是求絕對值），表示當(dāng)前 sum 距離更近，則更新結(jié)果 ans = sum
• 若 sum < target ，左指針 L 右移
• 若 sum > target，右指針 R 左移

代碼實現(xiàn)

//go
func?threeSumClosest(nums?[]int,?target?int)?int?{
?sort.Ints(nums)?//?排序
?length?:=?len(nums)
?ans?:=?nums[0]?+?nums[1]?+?nums[2]
?for?i?:=?0;?i???l,?r?:=?i+1,?length-1
??for?l????sum?:=?nums[i]?+?nums[l]?+?nums[r]
???if?AbsInt(target-sum)?????ans?=?sum
???}
???if?sum?????l++
???}?else?if?sum?>?target?{
????r--
???}?else?{
????return?ans
???}
??}
?}
?return?ans
}

func?AbsInt(x?int)?int?{
?if?x?0?{
??return?-x
?}
?return?x
}

//java
class?Solution?{
????public?int?threeSumClosest(int[]?nums,?int?target)?{
????????//?排序
????????Arrays.sort(nums);
????????int?closestNum?=?nums[0]?+?nums[1]?+?nums[2];
????????for?(int?i?=?0;?i?2;?i++)?{
????????????int?l?=?i?+?1,?r?=?nums.length?-?1;
????????????while?(l?????????????????int?threeSum?=?nums[l]?+?nums[r]?+?nums[i];
????????????????if?(Math.abs(threeSum?-?target)?????????????????????closestNum?=?threeSum;
????????????????}
????????????????if?(threeSum?>?target)?{
????????????????????r--;
????????????????}?else?if?(threeSum?????????????????????l++;
????????????????}?else?{
????????????????????//?如果已經(jīng)等于target的話,?肯定是最接近的
????????????????????return?target;
????????????????}

????????????}

????????}

????????return?closestNum;
????}

}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～