题解 | #三数之和#

1. 题目要求非降序输出，所以先排序
2. 遍历数组，转化成求两数之和
3. 数组也可以使用双指针，在一个有序的数组中使用双指针求两数之和
4. 注意去重

import java.util.*;


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

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

        int len = num.length;
        if (len < 3) {
            return res;
        }

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

            int left = i + 1;
            int right = len - 1;

            int target = -num[i];

            while (left < right) {
                if (num[left] + num[right] > target) {
                    right --;
                } else if (num[left] + num[right] < target) {
                    left++;
                } else if (num[left] + num[right] == target) {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[left]);

                    list.add(num[right]);

                    res.add(list);

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

        return res;
    }
}