LeetCode-15-3Sum-M（三数之和为0）_3sum 为0 leetcode

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解决方法：三指针法，注意要剪枝去掉可能重复的组合。

值得说明的是，对数组进行排序之后，每次循环的第一个指针指向的数字如果大于0，那么后面的任何三个数字肯定都不满足条件，因此在这里也要做一次剪枝处理。

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
        
        List<List<Integer>> res=new ArrayList<>();
        
        Arrays.sort(nums);
        for(int p1=0;p1<nums.length;p1++){
            if(nums[p1]>0)//如果第一个数大于0，说明后面的任何三个数字肯定都不能满足条件
                return res;
            if(p1>0 && nums[p1]==nums[p1-1])//为了去除重复组合
                continue;
            int p2=p1+1;
            int p3=nums.length-1;
            while(p2<p3){
                int a=nums[p1];
                int b=nums[p2];
                int c=nums[p3];
                if(b+c==-a){
                    List<Integer> temp=new ArrayList<>();
                    temp.add(a);
                    temp.add(b);
                    temp.add(c);
                    res.add(temp);
                    while(p2<p3 && nums[p2]==nums[p2+1])//为了去除重复组合
                        p2++;
                    while(p2<p3 && nums[p3]==nums[p3-1])//为了去除重复组合
                        p3--;
                    p2++;
                    p3--;
                }else if(b+c>-a){
                    p3--;
                }else{
                    p2++;
                }
            }            
        }       
        return res;
    }    
}
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