题解 | 三数之和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        if (num == null || num.length < 3) {
            return res;
        }
        Arrays.sort(num);

        // 遍历数组，固定第一个数 num[i] (即 a)
        for (int i = 0; i < num.length - 2; i++) {

            // 如果排好序后的第一个数都大于0，那后面全是正数，加起来绝对不可能等于0，直接结束
            if (num[i] > 0) break;

            // 如果当前的 a 和上一个 a 相同，说明这个组合我们查过了，跳过
            if (i > 0 && num[i] == num[i - 1]) continue;

            // 设置双指针，在 i 之后的区间寻找 b 和 c
            int left = i + 1;
            int right = num.length - 1;

            while (left < right) {
                int sum = num[i] + num[left] + num[right];

                if (sum == 0) {
                    // 找到了一组解，加入结果集
                    // asList语法糖，直接将这三个数放入结果中，但是要注意，这样的数组大小的固定的
                    // 需要使用ArrayList进行包装
                    res.add(new ArrayList<>(Arrays.asList(num[i], num[left], num[right])));

                    // 跳过相同的 b
                    while (left < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    // 跳过相同的 c
                    while (left < right && num[right] == num[right - 1]) {
                        right--;
                    }

                    // 找到解后，左右指针同时往中间收缩，继续寻找下一组可能的解
                    left++;
                    right--;
                } else if (sum < 0) {
                    // 和太小，左指针右移，让和变大
                    left++;
                } else {
                    // 和太大，右指针左移，让和变小
                    right--;
                }
            }
        }

        return res;
    }
}