LeetCode 16 最接近的三数之和
题目:
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
通过次数413,132提交次数908,668
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解:
此题使用双指针法为最优方案
具体流程如下:
1.对数组排序
2.遍历数组[0,nums.length-2)，i为当前遍历的位置,
定义L=i+1 R=nums.length-1，即L为i的下一位，R为数组末尾
定义minClose为最接近Target的距离，
定义sum为最接近Target的三数和
然后我们按照以下步骤寻找:
a.如果nums[i]+nums[L]+nums[R]-Target=0 直接返回结果
b.如果nums[i]+nums[L]+nums[R]-Target>0
比较三数和与Target距离和minClose，如果更接近则更新minClose和sum，
R左移使三数和与Target更接近
c.如果nums[i]+nums[L]+nums[R]-Target<0
比较三数和与Target距离和minClose，如果更接近则更新minClose和sum，
L右移使三数和与Target更接近
d.一旦L，R相遇则此次循环结束
3.剪枝:
a.如果某一次遍历中 nums[i]+nums[i+1]+nums[i+2] > Target，
说明此次遍历的最小和sumTemp > Target
那么我们可以断言，如果最小和sumTemp与Target之间的距离sumTemp-Target
比当前记录的最小距离minClose还要大，那么后续无论怎么移动L和R和只会增大，
sumTemp与Target的距离sumTemp-Target只会更大，
并且下一次遍历i+1开始也是如此，
因此后续所有遍历均没有必要，可以直接退出返回结果
b.如果某一次遍历中 nums[i]+nums[nums.length-2]+nums[nums.length-1] < Target，
说明此次遍历的最大和sumTemp < Target
那么我们可以断言，如果最大和sumTemp与Target之间的距离Target-sumTemp
比当前记录的最小距离minClose还要大，那么后续无论怎么移动L和R和只会减小，
sumTemp与Target的距离Target-sumTemp只会更大，
但是下一轮遍历i+1使得和会增大，因此后续遍历无法断言，
只可以终止当前循环，直接进入下一轮循环
图解:
例：nums = [3,5,-2,-1,8,10,15]
target = 9
定义变量如下:
sum = nums[0](-2)+nums[1](-1)+nums[2](3) = 0
minClose = |sum(0) - target(9)| = 9
第一轮遍历 [ i=0 minClose=9 sum=0 ]
首先判断不满足剪枝条件，开始循环
tempSum = nums[i](-2)+nums[L](-1)+nums[R](15) = 12
|tempSum(12) - target(9)| = 3 < minClose 替换原有的sum和minClose
此时 sum = 12 minClose = 3
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-2)+nums[L](-1)+nums[R](10) = 7
|tempSum(7) - target(9)| = 2 < minClose 替换原有的sum和minClose
此时 sum = 7 minClose = 2
由于tempSum < target L指针右移 ⬇
tempSum = nums[i](-2)+nums[L](3)+nums[R](10) = 11
|tempSum(11) - target(9)| = 2 = minClose 原有的sum和minClose不变
此时 sum = 7 minClose = 2
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-2)+nums[L](4)+nums[R](8) = 10
|tempSum(10) - target(9)| = 1 < minClose 替换原有的sum和minClose
此时 sum = 10 minClose = 1
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-2)+nums[L](4)+nums[R](5) = 7
|tempSum(7) - target(9)| = 2 > minClose 原有的sum和minClose不变
此时 sum = 10 minClose = 1
L,R相遇，此轮遍历结束
第二轮遍历 [ i=1 minClose=1 sum=10 ]
首先判断不满足剪枝条件，开始循环
tempSum = nums[i](-1)+nums[L](4)+nums[R](15) = 18
|tempSum(18) - target(9)| = 9 > minClose 原有的sum和minClose不变
此时 sum = 10 minClose = 1
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-1)+nums[L](4)+nums[R](10) = 13
|tempSum(13) - target(9)| = 4 > minClose 原有的sum和minClose不变
此时 sum = 10 minClose = 1
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-1)+nums[L](4)+nums[R](8) = 11
|tempSum(11) - target(9)| = 2 > minClose 原有的sum和minClose不变
此时 sum = 10 minClose = 1
由于tempSum > target R指针左移 ⬇
tempSum = nums[i](-1)+nums[L](4)+nums[R](5) = 8
|tempSum(8) - target(9)| = 1 = minClose 原有的sum和minClose不变
此时 sum = 10 minClose = 1
L,R相遇，此轮遍历结束
第三轮遍历 [ i=2 minClose=1 sum=10 ]
此时我们可以发现
最小和 minSum = nums[i](4)+nums[i+1](5)+nums[i+2](8) = 17 > target
并且最小和 minSum(17) - target(9) = 8 > minClose(1)
因此后续所有遍历和一定都大于17，直接返回结果即可
结果返回 sum=10
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| public int threeSumClosest_02(int[] nums, int target) {
int sumResult = nums[0] + nums[1] + nums[2];
int minClose = Math.abs(sumResult - target);
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
int maxV = nums[i] + nums[i + 1] + nums[i + 2];
if (maxV > target && maxV - target > minClose) {
break;
}
int minV = nums[i] + nums[nums.length - 1] + nums[nums.length - 2];
if (minV < target && target - minV > minClose) {
continue;
}
int L = i + 1;
int R = nums.length - 1;
while (L < R) {
int sum = nums[i] + nums[L] + nums[R];
if (sum == target) {
return sum;
} else if (sum > target) {
if (sum - target < minClose) {
minClose = sum - target;
sumResult = sum;
}
R--;
} else {
if (target - sum < minClose) {
minClose = target - sum;
sumResult = sum;
}
L++;
}
}
}
return sumResult;
}
|