原题地址：https://leetcode.cn/problems/3sum/
题解
首先对nums排序
一层循环：在nums里顺序遍历数i
二层循环：left和right指针分别设置在nums[i+1]——nums[length]两端
- 若i+left+right<0则说明需要更大的正数，left++，反之则right–
- 若i+left+right=0则将三元组加入List，然后left++，right–
去重：i、left、right推进时若读到重复数则跳过，以便去重
时间复杂度：O(N^2)
空间复杂度：O(1)
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans=new LinkedList<>();
List<Integer> tmp;
Arrays.sort(nums);
int j,k;
for(int i=0;i<nums.length&&nums[i]<=0;i++){
if(i>0&&nums[i]==nums[i-1])continue;
j=i+1;
k=nums.length-1;
tmp=new LinkedList<>();
while (j<k){
if(nums[i]+nums[j]+nums[k]==0){
tmp.add(nums[i]);
tmp.add(nums[j]);
tmp.add(nums[k]);
ans.add(tmp);
tmp=new LinkedList<>();
j++;
while(j<k&&nums[j]==nums[j-1])j++;
k--;
while(j<k&&nums[k]==nums[k+1])k--;
}else if(nums[i]+nums[j]+nums[k]<0){
j++;
}else{
k--;
}
}
}
return ans;
}
}
|
