题解 | #数组中相加和为0的三元组#

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        
        if(num == null || num.length < 3){
            return new ArrayList<ArrayList<Integer>>();
        }
        //1.排序
        Arrays.sort(num);
        if(num[0] > 0){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        //1.暴力破解法
//         for(int i = 0;i< num.length - 2;i++){
//             for(int j = i + 1;j<num.length -1;j++){
//                 for(int k = j+ 1; k< num.length;k++){
//                     if(num[i] +num[j] + num[k] == 0){
//                         ArrayList<Integer> ele = new ArrayList<>();
//                         ele.add(num[i]);
//                         ele.add(num[j]);
//                         ele.add(num[k]);
//                         ele.sort((x,y) -> x-y);
//                         if(!result.contains(ele)){
//                             result.add(ele);
//                         }
//                     }
//                 }
//             }
//         }
        //i...j...k
        int n = num.length;
        //2.方法二，两路指针，往中间夹定律
        for(int i = 0;i< n-2;i++){
            //如果前一个数和当前数一样，去重，不需要判断了
            if(i > 0 && num[i-1] == num[i]){
                continue;
            }
            //数组最右边
            int k = n - 1;
            //在i到k间找一个数 相加为0 
            for(int j = i+1 ; j<k;){
                if(j >i+1 && num[j-1] == num[j]){
                    j++;
                    continue;
                }
                if(k < n-1 && num[k+1] == num[k]){
                    k--;
                    continue;
                }
                int sum = num[i] + num[j] + num[k];
                if(sum == 0){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[j]);
                    list.add(num[k]);
                    result.add(list);
                    j++;
                    k--;
                }else if(sum > 0){
                    //说明 右边边界有点大， 窗口大小向左移
                    k--;
                }else{
                    j ++;
                }
            }
        }
        
        
        return result;
    }
}