16. 最接近的三數(shù)之和

給你一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 nums 和 一個(gè)目標(biāo)值 target。請(qǐng)你從 nums 中選出三個(gè)整數(shù)，使它們的和與 target 最接近。
返回這三個(gè)數(shù)的和。
假定每組輸入只存在恰好一個(gè)解。

排序 + 雙指針

思路同15. 三數(shù)之和

簡(jiǎn)單地使用三重循環(huán)枚舉所有的三元組時(shí)間復(fù)雜度為O(n^3)，時(shí)間及空間復(fù)雜度均不滿足我們使用的需求。
若我們枚舉的三元組 (a,b,c) 滿足a≤b≤c，保證了只有 (a,b,c)這個(gè)順序會(huì)被枚舉到，而 (b,a,c)、(c,b,a) 等等這些不會(huì)，這樣就減少了重復(fù)。
可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素 a和 b，那么只有唯一的 c滿足 a+b+c≈target。當(dāng)?shù)诙匮h(huán)往后枚舉一個(gè)元素 b′ 時(shí)，由于 b′>b，那么滿足 a+b′+c′≈target的 c′一定有 c′<c, c′在數(shù)組中一定出現(xiàn)在 c 的左側(cè)。也就是說(shuō)，我們可以從小到大枚舉 b，同時(shí)從大到小枚舉 c，即第二重循環(huán)和第三重循環(huán)實(shí)際上是并列的關(guān)系。

因此，我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個(gè)從數(shù)組最右端開(kāi)始向左移動(dòng)的指針，這個(gè)思想就是「雙指針」。每次遍歷我們記錄一個(gè)結(jié)果，和target比較，隨著循環(huán)進(jìn)行，我們的結(jié)果必然無(wú)限接近這個(gè)target值。

優(yōu)化點(diǎn)：
1.每層遍歷注意去除相鄰重復(fù)的數(shù)字
2.若三數(shù)之和等于target，則直接返回，因?yàn)闆](méi)有比相等更接近的了[😂]
3.設(shè) i<cnt-2 && s = nums[i] + nums[i+1] + nums[i+2]。如果 s > target，由于數(shù)組已經(jīng)排序，后面無(wú)論怎么選，選出的三個(gè)數(shù)的和不會(huì)比 s 還小，所以不會(huì)找到比 s 更優(yōu)的答案了。所以只要 s > target，就可以直接 break 外層循環(huán)了。在 break 前判斷 s 是否離 target 更近，如果更近，那么更新 best 為 s。
4.設(shè) cnt > 1 && i<cnt-2 && s = nums[i] + nums[n-2] + nums[n-1]。如果 s < target，由于數(shù)組已經(jīng)排序，nums[i] 加上后面任意兩個(gè)數(shù)都不超過(guò) s，所以下面的雙指針就不需要跑了，無(wú)法找到比 s 更優(yōu)的答案。但是后面還有更大的 nums[i]，可能找到一個(gè)離 target 更近的三數(shù)之和，所以還需要繼續(xù)枚舉，continue 外層循環(huán)。在 continue 前判斷 s 是否離 target 更近，如果更近，那么更新 best 為 s。

知識(shí)點(diǎn)：「雙指針適用場(chǎng)景」當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時(shí)間復(fù)雜度從 O(n^2)降至O(n)。

總體時(shí)間復(fù)雜度：O(n^2), 排序時(shí)間復(fù)雜度為O(nlogn)，漸進(jìn)抵消
空間復(fù)雜度：O(logN)

Swift

func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {let sortedNum = nums.sorted()let cnt = sortedNum.countvar result: Int = Int(1e7)let updateValue = {(sum:Int) inif sum == 2938 {print("")}if abs(sum-target) < abs(result-target) {result = sum;}}for i in 0..<cnt {if i>0 && sortedNum[i] == sortedNum[i-1] {continue}//由于有序，后面無(wú)論怎么選，選出的三個(gè)數(shù)的和不會(huì)比 s 還小if i<cnt-2 && sortedNum[i]+sortedNum[i+1]+sortedNum[i+2]>=target {updateValue(sortedNum[i]+sortedNum[i+1]+sortedNum[i+2]);break}//由于數(shù)組已經(jīng)排序，nums[i] 加上后面任意兩個(gè)數(shù)都不超過(guò) s，所以下面的雙指針就不需要跑了，但i增大后存在可能，因此繼續(xù)外層if cnt > 1 && i<cnt-2 && sortedNum[i] + sortedNum[cnt-2] + sortedNum[cnt-1] < target {updateValue(sortedNum[i]+sortedNum[cnt-2]+sortedNum[cnt-1]);continue}var j=i+1, k=cnt-1while j < k {let s = sortedNum[i] + sortedNum[j] + sortedNum[k]if s == target {return target}updateValue(s);if s < target {var j0 = j+1;while j0<cnt && sortedNum[j0] == sortedNum[j0-1] {j0 += 1}j = j0}else {var k0 = k-1while k0 > 0 && sortedNum[k0] == sortedNum[k0+1] {k0 -= 1}k = k0}}}return result}

OC

-(NSInteger)threeSumClosest:(NSArray *)nums target:(NSInteger)target {if (nums.count < 3) {return 0;}//先排序NSArray *sortedNum = [nums sortedArrayUsingComparator:^NSComparisonResult(id  _Nonnull obj1, id  _Nonnull obj2) {return [obj1 compare:obj2];}];NSInteger cnt = sortedNum.count;__block NSInteger result = 1e7;void (^updateValue)(NSInteger) = ^(NSInteger sum) {if (labs(sum - target) < labs(result-target)) {result = sum;}};//開(kāi)始遍歷for (NSInteger i=0; i<cnt; i++) {//過(guò)濾重復(fù)的部分if (i>0 && sortedNum[i] == sortedNum[i-1]) {continue;}//由于有序，后面無(wú)論怎么選，選出的三個(gè)數(shù)的和不會(huì)比 s 還小if (i<cnt-2 && [sortedNum[i] integerValue] +[sortedNum[i+1] integerValue] + [sortedNum[i+2] integerValue] >= target) {updateValue([sortedNum[i] integerValue]+[sortedNum[i+1] integerValue] + [sortedNum[i+2] integerValue]);break;}//由于數(shù)組已經(jīng)排序，nums[i] 加上后面任意兩個(gè)數(shù)都不超過(guò) s，所以下面的雙指針就不需要跑了，但i增大后存在可能，因此繼續(xù)外層if (cnt > 1 && i<cnt-2 && [sortedNum[i] integerValue] + [sortedNum[cnt-2] integerValue]+ [sortedNum[cnt-1] integerValue] < target) {updateValue([sortedNum[i] integerValue]+[sortedNum[cnt-2] integerValue]+[sortedNum[cnt-1] integerValue]);continue;}NSInteger j=i+1, k=cnt-1;while (j<k) {NSInteger s = [sortedNum[i] integerValue] + [sortedNum[j] integerValue] + [sortedNum[k] integerValue];if (s == target) {return s;}updateValue(s);if(s < target) {NSInteger j0 = j+1;//過(guò)濾重復(fù)的部分while (j0 < cnt && [sortedNum[j0] integerValue] == [sortedNum[j0-1] integerValue]) {j0++;}j = j0;}else {NSInteger k0 = k-1;while (k0 > 0 && [sortedNum[k0] integerValue] == [sortedNum[k0+1] integerValue]) {k0--;}k = k0;}}}return result;
}