https://leetcode-cn.com/problems/3sum-closest/
感觉和上一题3Sum思路类似，先试试暴力解法。发现真的可以 run，不过效率非常低，算法需要改进。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int threeSumClosest(int[] nums, int target) {
int diff=Integer.MAX_VALUE;
int sum=0;
for(int i=0;i<nums.length-2;i++){
for(int j=i+1;j<nums.length-1;j++){
for(int k=j+1;k<nums.length;k++){
int s=nums[i]+nums[j]+nums[k];
int d=Math.abs(target-s);
if(d<diff){
diff=d;
sum=s;
}
}
}
}
return sum;
}
}
|
使用类似 3Sum 的双指针解法，效率提升了很多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int diff=Integer.MAX_VALUE;
int sum=0;
for(int i=0;i<nums.length-2;i++){
if(nums[i]>target && diff<Integer.MAX_VALUE) break;
int j=i+1,k=nums.length-1;
while(j<k){
int s=nums[i]+nums[j]+nums[k];
int d=Math.abs(target-s);
if(d<diff){
diff=d;
sum=s;
}
if(s<target) j++;
else if(s>target) k--;
else break;
}
}
return sum;
}
}
|
参考了最快的答案的剪枝操作，发现也没快多少。
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
| class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int diff=Integer.MAX_VALUE;
int sum=0;
for(int i=0;i<nums.length-2;i++){
if(i>0 && nums[i-1]==nums[i]) continue;
int t=nums[i]+nums[nums.length-1]+nums[nums.length-2];
if(t<target){
diff=target-t;
sum=t;
continue;
}
t=nums[i]+nums[i+1]+nums[i+2];
if(nums[i]*3>target){
if(t-target<diff) sum=t;
break;
}
if(nums[i]>target && diff<Integer.MAX_VALUE) break;
int j=i+1,k=nums.length-1;
while(j<k){
int s=nums[i]+nums[j]+nums[k];
int d=Math.abs(target-s);
if(d<diff){
diff=d;
sum=s;
}
if(s<target) j++;
else if(s>target) k--;
else break;
}
}
return sum;
}
}
|