题解 | #三数之和#

import java.util.*;
/**
 1、判断数组长度：num==null||num.length<3 ，返回空。
 2、排序：对数组升序排序
 3、遍历 num[i]：
    数组有序，所以num[i]>0，意味着后续都是大于0的，所以直接 break
    去重，当 num[i]=num[i-1] 时，跳出本次循环，执行下一次，continue；
    双指针法：left =i+1 ，right = num.length-1，
         num[i]+num[left]+num[right] =0，记录结果，
		              判断left是否和后一个元素相等，相等就 left++；
					  判断right是否和前一个元素相等，相等就 right--；
					  反之，left++， right--;
		 num[i]+num[left]+num[right] >0,说明num[right]的值大，所以 right--；
		 num[i]+num[left]+num[right] <0,说明num[left]的值小，所以 left++；
*/

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();

        if(num==null||num.length<3){
            return res;
        }

        Arrays.sort(num);

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

            if(i>0&&num[i]==num[i-1]){
                continue;
            }

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

            while(left<right){
                int sum = num[i]+num[left]+num[right];
                if(sum==0){
                    ArrayList<Integer> l =new ArrayList<>();
                    l.add(num[i]);
                    l.add(num[left]);
                    l.add(num[right]);
                    res.add(l);

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

                    left++;
                    right--;
                }else if(sum>0){
                    right--;
                }else{
                    left++;
                }
            }

        }
        return res;
    }
}