题解 | #三数之和#

public class Solution {
     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int n = num.length;
        if (n < 3) {
            return res;
        }
        ArrayList<Set<Integer>> temp = new ArrayList<>();
        Arrays.sort(num);//进行排序
        for (int i = 0; i < n; i++) {
            int cur = num[i];//当前记录值
            int left = 0;
            int right = n - 1;
            //在出去num[i]的子数组中寻找而和为-num[i]的二元组
            do {
                //如果与当前元素相等则指针移动
                if (left == i) {
                    left++;
                } else if (right == i) {
                    right--;
                }
                if (left < right) {
                    int val = cur + num[left] + num[right];//记录当前三元组的值
                    if (val == 0) {
                        //
                        Set<Integer> already = new HashSet<>();
                        already.add(cur);
                        already.add(num[left]);
                        already.add(num[right]);
                        //判断是否重复再添加
                        if (!temp.contains(already)) {
                            temp.add(already);
                        }
                        left++;
                        right--;
                    } else if (val < 0) {
                        left++;
                    } else if (val > 0) {
                        right--;
                    }
                }
            } while (left < right);
        }
        for (Set<Integer> set : temp) {
            ArrayList<Integer> t = new ArrayList<>();
            t.addAll(set);
            if (t.size()==1){
                t.add(0);
                t.add(0);
            }else if (t.size()<3){
                t.add(-t.get(0)-t.get(1));
            }
            t.sort(null);
            res.add(t);
        }
        return res;
    }
}