1.知识点:
- 双指针
- 数组排序(默认升序);自定义降序
2.排序代码
1 |
|
注意点:
Collections.reverseOrder() <!--1--> * 道理同上
自己重写 Comparator <!--2--> 才可以实现 用 int 类型直接排序(默认是升序列)
若要降序,基本都需要 Integer 类型;
若是 int 基础类型,那么需要手动 转换一下类型;
3.题目:
寻找数组中三个数字之和,要求和最接近于目标数值
法一:暴力:O($N^3$)
```java
//法一:暴力 O(n^3)
int best = 100000;
int diff = 100000;
for(int i=0;i<nums.length;i++){for(int j = i+1;j<nums.length;j++){ for(int k = j+1;k<nums.length;k++){ if(Math.abs(nums[i]+nums[j]+nums[k] - target) < diff){ diff = Math.abs(nums[i]+nums[j]+nums[k] - target); best = nums[i]+nums[j]+nums[k]; } } }
}
return best;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
45
46
47
48
49
50
51
52
53
54
55
56
57
*
* 法二:双指针:第一个元素从头到尾遍历,二、三元素从表头、尾向中间靠拢。
* 好处是:省掉了很多没必要的不可能组合;(有点剪枝的意思了)
```java
import java.util.*;
public class 最接近的三数之和_16 {
public static void main(String[] args) {
}
public int threeSumClosest(int[] nums, int target){
Arrays.sort(nums);//升序排列
int n = nums.length;
int best = 10001000;
for(int i = 0;i < n; i++){
//若下一个元素和当前元素内容一样,则可以跳过;
//continue,直接跳过当前循环,进入下一次循环;
if(i>0 && nums[i] == nums[i-1]){
continue;
}
//使用双指针,枚举 b 和 c;
int j = i+1, k = n-1;
while(j < k){
int sum = nums[i] + nums[j] + nums[k];
//如果直接等于target,那么直接返回,最接近;
if(sum == target){
return target;
}
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
if(sum > target){
int k0 = k - 1;
//开始移动 c 的指针,直到比原本的 c 值要小;
// 向左移动到下一个不想等的元素;
while(j < k0 && nums[k0] == nums[k]){
--k0;
}
k = k0; // 如果发生 k = k0 == j;那么会退出现在的 while(j < k)
}else{
//如果 sum < target,那么就把 b 指针向左移动;
int j0 = j+1;
while(j0 < k && nums[j0] == nums[j]){
++j0;
}
j = j0;
}
}
}
return best;
}
}