0%

刷算法(8)-最接近的三数之和

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
int diff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length-2; i++){
int left = i + 1;
int right = nums.length - 1;
while (left < right){
int sum = nums[i] + nums[left] + nums[right];
if (sum < target){
left++;
}else if(sum > target){
right--;
}else{
result = target;
return result;
}
if (Math.abs(sum -target) < diff){
diff = Math.abs(sum -target);
result = sum;
}
}
}
return result;

上面是最基本最正宗的解法,耗时11ms左右。

优化后解法2

当有相同数字时,如第i个等于第i-1个,进行剪枝操作跳过当前的i。

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
public int threeSumClosest2(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
int diff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; //剪枝去重

int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result = target;
return result;
}
if (Math.abs(sum - target) < diff) {
diff = Math.abs(sum - target);
result = sum;
}
}
}
return result;
}

经过优化后时间缩短到5ms。

优化后解法3

在上面2的基础上还可以进一步优化,排序后的数组对给定的索引i,在[left, right]区间内,最大值 rangeMax = nums[i] + nums[right] + nums[right - 1],最小值为 rangeMin = nums[i] + nums[left] + nums[left + 1]。如果最小值都比target大,那left右边的数一定比target大也就没有必要比下去了。因此只需判断rangeMin和target之间的diff是否最小,如果小的话更新diff和result。同理,针对区间内的最大值rangeMax如果它都比target小的话,那right右边的肯定都比target小,也没有比的必要了。只需要判断rangeMax和target之间的diff关系就行了。
总之:rangeMin和rangeMax是两种极端情况,让程序不再做无谓的循环比较。

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
40
41
42
43
44
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
int diff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;

int rangeMin = nums[i] + nums[left] + nums[left + 1];
int rangeMax = nums[i] + nums[right] + nums[right - 1];

if (rangeMin > target) {
if (Math.abs(rangeMin - target) < diff) {
diff = Math.abs(rangeMin - target);
result = rangeMin;
}
continue;
} else if (rangeMax < target) {
if (Math.abs(rangeMax - target) < diff) {
diff = Math.abs(rangeMax - target);
result = rangeMax;
}
continue;
}

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
result = target;
return result;
}
if (Math.abs(sum - target) < diff) {
diff = Math.abs(sum - target);
result = sum;
}
}
}
return result;
}

上述代码执行时间缩短到2ms。

三种解法时间对比

屏幕快照 2019-10-01 下午7.53.35.png

心得

  1. 一定要仔细读题,题目要求返回的是sum,和target最接近的求和,而不是diff;
  2. 进入循环后如果i和i-1值相同,一定要进行剪枝操作;
  3. 初始diff设成最大,之后不断修正成最小值;

参考