最接近的三數之和
- 題目描述
- 題解
- 總結
題目描述
給定一個包括 n 個整數的數組 nums 和 一個目标值 target。找出 nums 中的三個整數,使得它們的和與 target 最接近。傳回這三個數的和。假定每組輸入隻存在唯一答案。
示例:
輸入:nums = [-1,2,1,-4], target = 1
輸出:2
解釋:與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
題解
對于這題,最簡單粗暴的方式當然是直接枚舉三元組,這将帶來巨大的時間消耗,高達 O ( N 3 ) O(N^3) O(N3)。
我們可以采用數組排序+雙指針的方式來解。
首先将數組按從小到大的順序進行排序,以周遊的方式先确定第一個數字A,然後利用雙指針(L和R)來确定另外的兩個數字。L指向A後面的那個元素(B),R指向數組最後面的那個元素©。
如果 A+B+C<target,說明需要将數字調大一點,那麼将L++。
如果 A+B+C>target,說明需要将數字調小一點,那麼将R–。
當不再滿足 L<R 這個條件時,停止這次搜尋,開始下一輪周遊。
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int best=1e7 ;
int len = nums.size();
for(int i=0;i<=len-3;i++)
{
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int l=i+1;
int r=len-1;
while(l<r)
{
int sum = nums[i]+nums[l]+nums[r];
if(sum==target) return sum;
if(abs(sum-target)<abs(best-target))
{
best = sum;
}
if(sum<target)
{
l++;
}
else
if(sum>target)
{
r--;
}
}
}
return best;
}
};
總結
這個題目難度算是中等吧,類似的衍生題目還有三數之和,兩數之和。隻要摸清這個排序+雙指針的套路,應該都沒問題的。最後的時間複雜度為 O ( N 2 ) O(N^2) O(N2)。