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

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //1. 初始化
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(num == null || num.length < 3){
            return res;  
        }

        //2. 排序
        Arrays.sort(num);

        //3. i用于确定第一个数
        for(int i =0; i < num.length; i++){
            //3.1 因为已经排过序，若第一个数就大于0，三数之和肯定大于0。
            if(num[i] >  0){
                break;
            }

            //3.2 对第一个数进行去重
            if(i > 0 && num[i]==num[i-1]){
                continue;
            }

            //3.3 双指针夹逼寻找另外两个数
            int sum = -num[i];
            int left = i + 1;
            int right = num.length - 1;

            while(left < right){
                if(num[left] + num[right] == sum){
                    //1. 第一组结果
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    res.add(list);

                    //2. 寻找其他结果组，对left和right去重
                    while(left < right && num[left] == num[left+1]){
                        left++;
                    }
                     while(left < right && num[right] == num[right -1 ]){
                        right--;
                    }

                    left++;
                    right--;

                }else if(num[left] + num[right] > sum){
                    right--;
                }else if(num[left] + num[right] < sum){
                    left++;
                }
            }
        }

        return res;
    }
}