https://leetcode-cn.com/problems/3sum/
乍看一下没啥特别好的思路，先写一个 O(n^3)的思路。
有一个麻烦的地方是不允许重复，而且还要从小到大排列，所以直接先使用 sort 方法对数组排序，然后使用一个 Set 来确保其唯一性，不过很显然，复杂度太高，如果数组太大，直接超时。所以还得找复杂度低一些的方法。但是，这个问题还不能用 2-sum 里的 HashMap 解决，原因有二：第一，顺序和去重问题很麻烦，第二，复杂度可能还是挺高。
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret= new ArrayList<>();
if(nums==null || nums.length<3) return ret;
Arrays.sort(nums);
Set<String> record=new HashSet<>();
for(int i=0;i<nums.length-2;i++){
for(int j=i+1;j<nums.length-1;j++){
for(int k=j+1;k<nums.length;k++){
if(nums[i]+nums[j]+nums[k]==0){
List<Integer> t=new ArrayList<Integer>();
t.add(nums[i]);
t.add(nums[j]);
t.add(nums[k]);
String t_s=t.toString();
if(!record.contains(t_s)){
record.add(t_s);
ret.add(t);
}
}
}
}
}
return ret;
}
}
|
看了一下网上的解法，才明白其中的奥秘。
首先还是需要对数组进行排序，然后通过固定第一个数字外加两个指向第二三两个数字的指针来完成。固定完第一个数字以后，后面两个数字分别从左边和右边开始，因为数组是从小到大顺序排列的，所以如果三个数字的和大于 0，说明右边的指针应该左移，反之，左边的指针应该右移。
另外就是判断重复值，对于固定的数字，如果后面的数字和它相同，那么说明需要跳过，对于后面两个指针指向的数字，需要用一个临时变量存放，如果下一次变化和之前的重复，则说明应该跳过。
最后就是一些剪枝操作：第一，如果数组长度小于 3，直接返回空，第二，如果固定的数字大于 0（而数组是顺序排列的），那么就不可能再有合适的结果了。
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ret=new ArrayList<>();
for(int i=0;i<nums.length-2;i++){
if(nums[i]>0) break;
if(i>0 && nums[i-1]==nums[i]) continue;
int j=i+1,k=nums.length-1;
while(j<k){
int t=nums[i]+nums[j]+nums[k];
if(t==0){
List<Integer> al=new ArrayList<>();
al.add(nums[i]);
al.add(nums[j]);
al.add(nums[k]);
ret.add(al);
int tj=nums[j],tk=nums[k];
while(tj==nums[j] && j<k) j++;
while(tk==nums[k] && j<k) k--;
}else if(t>0){
k--;
}
else{
j++;
}
}
}
return ret;
}
}
|