题解 | #三数之和#

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // 双指针法，先排序num, num中从左到右取一值num[i]，双指针从剩下数组值中取出两个数和num[i]相加为0,记得去重！
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        //num长度少于3，返回空数组
        int n = num.length;
        if(n < 3) return ret;
        Arrays.sort(num);
        for(int i = 0; i < n - 2; i++){
            if(i != 0 && num[i] == num[i - 1]) continue;
            int target = -num[i];
            int left = i + 1, right = n - 1;
            while(left < right){
                if(num[left] + num[right] == target){
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(-target);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    ret.add(temp);
				  //去重
                    while(num[left] == num[left + 1] && left + 1 < right) left++;
                    while(num[right] == num[right - 1] && left  < right - 1) right--;
                    //双指针向中间收缩
                    left++;
                    right--;
                }
			  //双指针指向的二值相加大于目标，右指针向左
                else if(num[left] + num[right] > target)
                    right--;
                //双指针指向的二值相加小于目标，左指针向右
                else
                    left++;
            }
        }
        return ret;
    }
}