知乎ID: 碼蹄疾
碼蹄疾，畢業(yè)于哈爾濱工業(yè)大學(xué)铺然。
小米廣告第三代廣告引擎的設(shè)計(jì)者俗孝、開發(fā)者；
負(fù)責(zé)小米應(yīng)用商店魄健、日歷赋铝、開屏廣告業(yè)務(wù)線研發(fā)；
主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)沽瘦；
關(guān)注推薦革骨、搜索、廣告領(lǐng)域相關(guān)知識(shí);
題目
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target析恋。找出 nums 中的三個(gè)整數(shù)苛蒲，使得它們的和與 target 最接近。返回這三個(gè)數(shù)的和绿满。假定每組輸入只存在唯一答案臂外。
例如，給定數(shù)組 nums = [-1喇颁，2漏健，1，-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. (-1 + 2 + 1 = 2).
分析
排序橘霎，和上一道題類似然后把三個(gè)數(shù)求和的解就轉(zhuǎn)化為兩個(gè)數(shù)相加等于某個(gè)數(shù)蔫浆。
求解兩個(gè)數(shù)相加等于某個(gè)數(shù)，用雙指針法即可姐叁。不需要處理重復(fù)問題瓦盛，還降低了難度。
Code
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
int l = i + 1;
int r = nums.length - 1;
while (l < r) {
int current = nums[i] + nums[l] + nums[r];
if (Math.abs(res - target) > Math.abs(target - current)) {
res = current;
}
if (current < target) {
l++;
} else {
r--;
}
}
}
return res;
}
}
掃碼關(guān)注
