forked from zfman/AlgorithmCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution15.java
More file actions
83 lines (76 loc) · 2.33 KB
/
Copy pathSolution15.java
File metadata and controls
83 lines (76 loc) · 2.33 KB
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package leetcode.all.solution1_100;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 15. 三数之和
*
* 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
*
* 注意：答案中不可以包含重复的三元组。
*
* 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
*
* 满足要求的三元组集合为：
* [
* [-1, 0, 1],
* [-1, -1, 2]
* ]
*
* @author 刘壮飞
* https://github.com/zfman.
* https://blog.csdn.net/lzhuangfei.
*/
public class Solution15 {
/**
* 双指针：先排序，然后指定第一个数，求解后面两数之和等于该数的相反数
* i指向第一个数之后的一个数，j指向末尾
* 如果此时三数之和等于0，那么将三个数记录
* 如果三数之和>0，j向前移动
* 如果三数之和<0，i向后移动
*
* 注意去重
*
* @param nums
* @return
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> r=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int k=i+1;//前指针：指向第2个数
int v=nums.length-1;//后指针：指向第3个数
if(nums[i]>0) continue;
//以下一行用来去重
if(i>0&&nums[i]==nums[i-1]) continue;
while(k<v){
int sum=nums[i]+nums[k]+nums[v];
if(sum==0){
r.add(Arrays.asList(nums[i],nums[k],nums[v]));
//以下两行用来去重
while(k<v&&nums[k]==nums[k+1]) k++;
while(k<v&&nums[v]==nums[v-1]) v--;
v--;
k++;
}else if(sum>0){
v--;
}else{
k++;
}
}
}
return r;
}
public static void main(String[] args){
int[] nums={
-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0
};
List<List<Integer>> r=new Solution15().threeSum(nums);
for(List<Integer> l:r){
for(Integer i:l){
System.out.print(i+" ");
}
System.out.println();
}
}
}