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

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(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

題解

• 本題目因為要計算三個數(shù)，如果靠暴力枚舉的話時間復(fù)雜度會到 O(n3)

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

• 在數(shù)組 nums 中，進行遍歷，每遍歷一個值利用其下標(biāo)i，形成一個固定值 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

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

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

• 總時間復(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;
????}
}

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