forked from JadeZYX/Java_LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP0015Sum3.java
More file actions
158 lines (155 loc) · 6 KB
/
Copy pathP0015Sum3.java
File metadata and controls
158 lines (155 loc) · 6 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class P0015Sum3 {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> ans = new ArrayList<>();
if(nums.length<3){
return ans;
}
Arrays.sort(nums);
int len = nums.length;
for(int i=0;i<len;i++){
if(i>0&&nums[i]==nums[i-1])continue;//题目中要求的去重复
int target=0-nums[i];
int j=i+1,k=len-1;//双向指针
while(j!=k){//双向指针循环条件，内部的while循环都是在去重复
//List<Integer>list=new ArrayList<>();
if(nums[j]+nums[k]==target){
ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
// list.add(nums[i]);
// list.add(nums[j]);
// list.add(nums[k]);
// ans.add(list);
j++;
k--;
while(j!=k&&nums[j]==nums[j-1]) j++;
while(j!=k&&nums[k]==nums[k+1]) k--;
}
else if(nums[j]+nums[k]>target){
k--;
while(j!=k&&nums[k]==nums[k+1]) k--;
}
else{
j++;
while(j!=k&&nums[j]==nums[j-1]) j--;
}
}
}
return ans;
}
public List<List<Integer>>threeSum1(int[]nums){
List<List<Integer>>list=new ArrayList<>();
Arrays.sort(nums);
for(int a=0;a<nums.length-2;a++){
if (a > 0 && nums[a] == nums[a-1]) continue;
for(int b=a+1;b<nums.length-1;b++){
if (b > a+1 && nums[b] == nums[b-1]) continue;
int c=(nums[a]+nums[b])*-1;
if (binarysearch(nums,b+1,nums.length,c)){
list.add(Arrays.asList(nums[a], nums[b], c));
}
}
}
return list;
}
public boolean binarysearch(int[]nums,int left,int right,int target){
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return true;
}
else if(nums[mid]>target){
right=mid;
}
else{
left=mid+1;
}
}
return false;
}
public List<List<Integer>> threeSum2(int[] nums) {
List<List<Integer>>list = new ArrayList<>();
if(nums.length<3 || nums==null)return list;//corner case
Arrays.sort(nums);//O(n*logn)
for(int i = 0;i<nums.length;i++){//o(n)
int currentNum = nums[i];
//第一次去重，比如[-2,0,0,2,2],当取0作为第一个数的时候，index=3的时候再次出现0可作为第一个数，所以需要判断
if(i>0 && nums[i-1]== currentNum) continue;
if(nums[i]>0) return list;//如果当前数已经大于0了，数组是有序排序，所以不会存在三个数相加等于0
int target = 0-currentNum;
int leftPoint = i+1;
int rightPoint = nums.length-1;
while(leftPoint<rightPoint ){
//避免重复[-1,0,1,2,-1,-4,-2,-3,3,0,4]->[-4,-3,-3,-1,-1,0,0,1,2,3]:
//当-4作为第一个数，-3作为第二个数时候，原数组-3的后面还是-3，没必要再进行一次查找
//但是当-3作为第一个数时，第二个数-3是不能skip的，所以不能用leftPoint>1这个条件作为限定,只能是leftPoint-1>i,也就是第一个数所在的位置
if(leftPoint-1>i && nums[leftPoint]==nums[leftPoint-1]){
leftPoint++;
}
else if(nums[leftPoint]+nums[rightPoint]==target){
list.add(Arrays.asList(currentNum,nums[leftPoint],nums[rightPoint]));
leftPoint++;
rightPoint--;
}
else if(nums[leftPoint]+nums[rightPoint]<target){
leftPoint++;
}
else {
rightPoint--;
}
}
}
return list;
}
public List<List<Integer>> threeSum4(int[] nums) {
List<List<Integer>>res = new ArrayList<>();
if(nums.length<3)return res;
Arrays.sort(nums);
for(int i = 0; i<nums.length-2;i++){
if(i>0 && nums[i-1]==nums[i])continue;
if(nums[i]>0)return res;
int target = 0-nums[i];
int left = i+1;
int right = nums.length-1;
while(left<nums.length-1 && left<right){
if(nums[left]+nums[right]==target){
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
while(left<right && nums[left]==nums[left-1]){//这里判定重复的时候必须用left<right，因为【0，0，0】，left会不断的➕超出length
left++;
}
while(left<right && nums[right]==nums[right+1]){
right--;
}
}
else if(nums[left]+nums[right]>target){
right--;
while(left<right && nums[right]==nums[right+1]){
right--;
}
}
else{
left++;
while(left<right && nums[left]==nums[left-1]){
left++;
}
}
}
}
return res;
}
}
/*
P0015Sum3 p15=new P0015Sum3();
List<List<Integer>>res=new ArrayList<>();
res=p15.threeSum(new int[]{-1,0,1,2,-1,-4});
for(List<Integer> list:res){
for(int num:list){
System.out.print(num);
}
}
P0015Sum3 p15 = new P0015Sum3();
System.out.println(p15.threeSum2(new int[]{-1,0,1,2,-1,-4}));
*/