题解 | #三数之和#

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        // 解题思路：
        // 1.如果数组长度小于3，则直接返回。
        // 2.对数组升序排序。
        // 3.采用双指针，left/right
        // 如果left + right == target,则left++，right--
        //  如果left+1 == left，则继续left++
        //  如果right-1 == right，则继续right--
        //  如果lef + right < target，则left++
        //  如果left + right > target，则right--
        if (num.length < 3) {
            return new ArrayList<>();
        }

        Arrays.sort(num);

        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();

        for (int i = 0; i < num.length - 2; i++) {
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = num.length - 1;

            while (left < right) {
                if (num[left] + num[right] == -num[i]) {
                    ArrayList<Integer> subList = new ArrayList<>();
                    subList.add(num[i]);
                    subList.add(num[left]);
                    subList.add(num[right]);
                    arrayList.add(subList);

                    while (num[left + 1] == num[left] && left + 1 < right) {
                        left++;
                    }

                    while (num[right - 1] == num[right] && right - 1 > left) {
                        right--;
                    }

                    left++;
                    right--;
                }

                if (num[left] + num[right] < -num[i]) {
                    left++;
                }

                if (num[left] + num[right] > -num[i]) {
                    right--;
                }
            }
        }

        return arrayList;
    }
}