16. 最接近的三數(shù)之和(雙指針)
做LeetCode16題有感材部,雙指針,即有兩個指針唯竹,一般指向一前一后乐导,如果有三個變量則固定一個,另外兩個變量使用雙指針浸颓。
舉例物臂,a+b+c=target。a产上、b棵磷、c是三個指針,我們可以固定a晋涣,移動指針b和c仪媒。
轉(zhuǎn)換成b+c=target-a。這樣就把a固定下來了
說完了雙指針的基本原理谢鹊,來做一道題算吩,即LC的第16題
首先將數(shù)組排序留凭,然后枚舉指針b和c,對特殊情況進行判斷偎巢,下面是代碼
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int l = nums.length;
int res = nums[0] + nums[1] + nums[2];
for (int i = 0; i < l - 2; i++) {
//防止重復
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = l - 1;
while (j < k) {
//當前的和
int sum = nums[i] + nums[j] + nums[k];
//如果sum==target直接返回
if (target == sum) return target;
//根據(jù)絕對值差值的大小來調(diào)整指針的位置
if (Math.abs(sum - target) < Math.abs(res - target)) {
res = sum;
}
if (sum > target) k--;
else j++;
}
}
return res;
}
}
其他細節(jié):如果指針移動過程中有重復項蔼夜,那么可以連續(xù)移動b和c指針
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int l = nums.length;
int res = nums[0] + nums[1] + nums[2];
for (int i = 0; i < l - 2; i++) {
//防止重復
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = l - 1;
while (j < k) {
//當前的和
int sum = nums[i] + nums[j] + nums[k];
//如果sum==target直接返回
if (target == sum) return target;
//根據(jù)絕對值差值的大小來調(diào)整指針的位置
if (Math.abs(sum - target) < Math.abs(res - target)) {
res = sum;
}
if (sum > target) {
k--;
while (j<k && nums[k] == nums[k + 1])
k--;
} else {
j++;
while (j<k&&nums[j]==nums[j-1]){
j++;
}
}
}
}
return res;
}
}