BM54题解 | #三数之和#

双指针

第一层for loop固定一个数，从这个数之后的部分中使用双指针，把问题优化成：一层遍历 + 两数之和

两个指针 left 和 right分别从子数组的左右出发，num[left] + num[right]小了就把left往右移动，大了就把right往左移动

当然，根据题意，还要进行去重操作 eg: [-2, 0, 0, 2, 2]，所以在判断到满足条件的left和right的时候，要将left移到最右边那个0（num[2]），right移到最左边那个2(num[3])，不然就会出现重复结果

这题也可以使用一层遍历 + Map/Set来做，但是去重操作没有双指针这么方便（left判断下一位的值是否和当前位的相等，并且下一位在right左边，right同理）

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<>();
        int len = num.length;
        if (len < 3) return res;
        Arrays.sort(num);
        // 遍历所有num[]中的数，除了最后两个
        for (int i = 0; i < len - 2; ++i) {
            // 有一样的就不需要遍历
            if (i != 0 && num[i - 1] == num[i]) continue;
            // 每个数对应的结果(如果有的话)
            int left = i + 1;
            int right = len - 1;
            int target = (-1) * num[i];
            while (left < right) {
                if (num[left] + num[right] == target) {
                    ArrayList<Integer> li = new ArrayList<>();
                    li.add(num[i]);
                    li.add(num[left]);
                    li.add(num[right]);
                    res.add(li);
                    // 因为可能存在 a, a, b的情况，所以要去重
                    // 因为最后left和right都是进行了++或者--之后再比较是否符合要求的，此时left或right已经改过了
                    // 所以要在修改之前把left和right对应的元素存入结果列表中
                    while (left + 1 < right && num[left] == num[left+1]) {
                        left++;
                    }
                    while (left < right - 1 && num[right] == num[right-1]) {
                        right--;
                    }
                    // 这个num[i]还可能有别的组合，需要继续深搜
                    left++;
                    right--;
                }
                if (num[left] + num[right] < target) {
                    left++;
                }
                if (num[left] + num[right] > target) {
                    right--;
                }
            }
        }
        return res;
    }
}