-
Notifications
You must be signed in to change notification settings - Fork 0
/
_3_sum.java
101 lines (98 loc) · 2.37 KB
/
_3_sum.java
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
import java.util.*;
public class _3_sum {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> res = new HashSet<>();
if(nums.length==0) return new ArrayList<>(res);
Arrays.sort(nums);
for(int i=0; i<nums.length-2;i++){
int j =i+1;
int k = nums.length-1;
while(j<k){
int sum = nums[i]+nums[j]+nums[k];
if(sum==0)res.add(Arrays.asList(nums[i],nums[j++],nums[k--]));
else if (sum >0) k--;
else if (sum<0) j++;
}
}
return new ArrayList<>(res);
}
}// class Solution {
//public List<List<Integer>> threeSum(int[] nums) {
//List<List<Integer>> ans = new ArrayList<>();
//Arrays.sort(nums);
//for (int i = 0 ; i < nums.length - 2; i++) {
// if (i > 0 && nums[i] == nums[i-1]) {
// continue;
// }
// int j = i + 1;
// int k = nums.length - 1;
// while (j<k){
// int sum = nums[i] + nums[j] + nums[k];
// if (sum == 0){
// List<Integer> li = new ArrayList<>();
// li.add(nums[i]);
// li.add(nums[j]);
// li.add(nums[k]);
// ans.add(li);
// while (j<k && nums[j] == nums[j+1]){
// j++;
// }
// while (j<k && nums[k] == nums[k-1]){
// k--;
// }
// j++;
// k--;
// } else if (sum<0){
// j++;
// } else{
// k--;
// }
// }
//}
//return ans;
//}
//}
class Solutiossssn {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
boolean[] bitmap = new boolean[100001];
for (int n : nums) {
if (n > 0) {
bitmap[n] = true;
}
}
ArrayList<List<Integer>> result = new ArrayList();
int f = -10000000;
int s = -10000000;
int max = nums[nums.length - 1];
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] == f) {
continue;
}
f = nums[i];
if (f > 0) {
break;
}
for (int j = i + 1; j < nums.length - 1; j++) {
if (nums[j] == s) {
continue;
}
s = nums[j];
int req = 0 - f - s;
if (req > max) {
continue;
}
if (req < 0) {
break;
}
if (req == s && nums[j + 1] == s) {
result.add(List.of(f, s, req));
}
else if (req > s && bitmap[req]) {
result.add(List.of(f, s, req));
}
}
}
return result;
}
}