题解 | #三数之和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // 先排序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            // 相同的数已判断过，直接跳过
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }

            // 以O(n)时间复杂度计算两数之和，双指针
            int target = 0 - num[i];
            int left = i + 1;
            int right = num.length - 1;
            while (left < right) {
                // 相同数已判断过，跳过
                if (left > i + 1 && num[left] == num[left - 1]) {
                    left++;
                    continue;
                }
                if (right < num.length - 1 && num[right] == num[right + 1]) {
                    right--;
                    continue;
                }
                int sum = num[left] + num[right];

                // 找到一个答案
                if (sum == target) {
                    ArrayList<Integer> ans = new ArrayList<>();
                    ans.add(num[i]);
                    ans.add(num[left]);
                    ans.add(num[right]);
                    res.add(ans);
                    left++;
                    continue;
                }

                // 如果和比目标小，右移左指针，否做左移右指针
                if (sum < target) {
                    left++;
                }else {
                    right--;
                }
            }
        }
        return res;
    }
}