题解 | #三数之和#

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length < 3) return (ArrayList)result;

        // 排序--单调递增
        Arrays.sort(num);

        // 遍历判断和是否0
        for (int i = 0; i < num.length - 2; i++) {
            if (num[i] > 0) break; // 大于0之间pass,不可能和为0
            if (i > 0 && num[i] == num[i - 1]) continue; // 重复排除掉

            // 双指针比较
            int lIdx = i + 1;
            int rIdx = num.length - 1;
            // 目标总和，是第 i 个的取反，也就是 a+b+c=0,则 b+c=-a 即可
            int target = -num[i];
            while (lIdx < rIdx) {
                if (num[lIdx] + num[rIdx] == target) {
                    // 相等，说明为0
                    result.add(new ArrayList<>(Arrays.asList(num[i], num[lIdx], num[rIdx])));
                    lIdx++;
                    rIdx--;
                    // 去重
                    while (lIdx < rIdx && num[lIdx] == num[lIdx - 1]) lIdx++;
                    while (lIdx < rIdx && num[rIdx] == num[rIdx + 1]) rIdx--;
                } else if ((num[lIdx] + num[rIdx] < target)) {
                    // 小于，左指针+1
                    lIdx++;
                } else {
                    // 大于，右指针-1
                    rIdx--;
                }
            }
        }
        return result;
    }
}

解题思想：排序+双指针