-
Notifications
You must be signed in to change notification settings - Fork 0
/
15. 3Sum.java
38 lines (38 loc) · 1.45 KB
/
15. 3Sum.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
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for(int i=0;i<n;i++){
int a = nums[i];
int target = -a;
int start = i+1;
int end = n-1;
while(start < end){
if(nums[start] + nums[end] == target){
List<Integer> res = new ArrayList<>();
res.add(nums[i]);
res.add(nums[start]);
res.add(nums[end]);
ans.add(res);
while(start < end && nums[start] == nums[start+1]){
start++;
}
while(start < end && nums[end] == nums[end-1]){
end--;
}
start++;
end--;
}else if(nums[start] + nums[end] > target){
end--;
}else{
start++;
}
}
while(i+1 < n && nums[i+1] == nums[i]){
i++;
}
}
return ans;
}
}