3数之和（LC134）

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。
例如，给定的数组 S = {-1 0 1 2 -1 -4},解集为(-1, 0, 1) (-1, -1, 2)

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        if(num.length == 3){
            if(num[0] + num[1] + num[2] == 0){
                ArrayList<Integer> al = new ArrayList<>();
                al.add(num[0]);
                al.add(num[1]);
                al.add(num[2]);
                result.add(al);
            }
            return result;
        }
        for(int i=0;i<num.length;i++){
            if(num[0] >0){
                break;
            }
            if(num[num.length-1] <0){
                break;
            }
            //当左指针都大于0，其他两个数再左指针右面会更大，所以这种类型直接break
            if(num[i] > 0){
                break;
            }
            if(i==0||num[i]>num[i-1]){
                int j=i+1;
                int k=num.length-1;
                while(j<k){
                    if(num[i]+num[j]+num[k]==0){
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[k]);
                        result.add(list);
                        j++;
                        k--;
                        //去除重复
                        while(j<k&&num[j]==num[j-1]){
                            j++;
                        }
                        //去除重复
                        while(j<k&&num[k]==num[k+1]){
                            k--;
                        }
                    }else if(num[i]+num[j]+num[k]<0){
                        j++;
                    }else{
                        k--;
                    }
                }
            }
        }
        return result;
    }
}