[数据结构与算法]三数和（力扣题）

??给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？
?即 ? a+b=-c
?请你找出所有和为 0 且不重复的三元组。
?注意：答案中不可以包含重复的三元组。
?示例 1：
?输入：nums = [-1,0,1,2,-1,-4]
?输出：[[-1,-1,2],[-1,0,1]]

看了题解才写出的代码：

思路；1：暴力求解，即三个 for循环，一次遍历最终得到结果，这里不说明

思路 2：双指针法，（这个我没想到，看代码才明白的）精辟！！！

? ? /**
? ? ?* 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
? ? ?* 对数组进行排序。
? ? ?* 遍历排序后数组：
? ? ?* 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
? ? ?* 对于重复元素：跳过，避免出现重复解
? ? ?* 令左指针 L=i+1，右指针 R=n?1，当 L<R 时，执行循环：
? ? ?* 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
? ? ?* 若和大于 0，说明 nums[R] 太大，R 左移
? ? ?* 若和小于 0，说明 nums[L] 太小，L 右移
? ? ?*/

根据题解写出代码为：

    public List<List<Integer>> threeSum(int[] a) {
        List<List<Integer>> lists = new ArrayList<>();
        //排序
        Arrays.sort(a); //排序
        //双指针

        for (int i = 0; i < a.length - 2; ++i) {
            if (a[i] > 0) return lists;//如果其中一个数大于0，不必考虑，和肯定大于0

            if (i > 0 && a[i] == a[i - 1]) continue;//跳出本次循环，进行下一次循环。避免出现重复解

            int L = i + 1, R = a.length - 1;
            while (L < R) {
                int sum = a[i] + a[L] + a[R];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(a[i]);
                    list.add(a[L]);
                    list.add(a[R]);
                    lists.add(list);
                    while (L < R && a[L + 1] == a[L]) ++L;
                    while (L < R && a[R - 1] == a[R]) --R;
                    ++L;
                    --R;
                } else if (sum < 0) {
                    ++L;
                } else {
                    --R;
                }
            }
        }
        return lists;
    }
}

我这里给出测试：

    @Test
    public void test() {
        int a[] = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum(a);
        for (List<Integer> list : lists) {
            System.out.println(list + " ");
        }

运行结果为：

?