?LeetCode刷題實(shí)戰(zhàn)16: 最接近的三數(shù)之和

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做最接近的三數(shù)之和?，我們先來看題面：

https://leetcode-cn.com/problems/3sum-closest/

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

題意

樣例

示例：

輸入：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

題解

• 本題目因?yàn)橐?jì)算三個(gè)數(shù)，如果靠暴力枚舉的話時(shí)間復(fù)雜度會到 O(n3)

• 首先進(jìn)行數(shù)組排序，時(shí)間復(fù)雜度O(nlogn)

• 在數(shù)組 nums 中，進(jìn)行遍歷，每遍歷一個(gè)值利用其下標(biāo)i，形成一個(gè)固定值 nums[i]

• 再使用前指針指向 start = i + 1 處，后指針指向 end = nums.length - 1 處，也就是結(jié)尾處

• 根據(jù) sum = nums[i] + nums[start] + nums[end] 的結(jié)果，判斷 sum 與目標(biāo) target 的距離，如果更近則更新結(jié)果 ans

• 同時(shí)判斷 sum 與 target 的大小關(guān)系，因?yàn)閿?shù)組有序，如果 sum > target 則 end--，如果 sum < target 則 start++，如果 sum == target 則說明距離為 0 直接返回結(jié)果

• 整個(gè)遍歷過程，固定值為 n 次，雙指針為 n 次，時(shí)間復(fù)雜度為 O(n2)

• 總時(shí)間復(fù)雜度：O(nlogn) + O(n2) = O(n2)

O(n^2)

class?Solution?{
????public?int?threeSumClosest(int[] nums, int?target)?{
????????Arrays.sort(nums);
????????int?ans = nums[0] + nums[1] + nums[2];
????????for(int?i=0;i????????????int?start = i+1, end = nums.length - 1;
????????????while(start < end) {
????????????????int?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;
????}
}

今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。