题解 | #三数之和#

//   从Leetcode取经而来


import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);                                        //排序数组，也可以不用sort，另写排序也可以
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();     //返回的结果集
        
        for(int k=0;k<num.length-2;k++){
            if(num[k]>0) break;    //当num[k]>0,k是k、i、j中最小的，所以直接跳出循环了
            if(k>0 && num[k]==num[k-1]) continue; // 重复则跳过
            
            int i=k+1,j=num.length-1;
            while(i<j){
                int sum=num[k]+num[i]+num[j];   //三数之和
                //因为已经排序了，所以sum>0时，j要左移使得三数和趋向0；同理，sum<0时，i要右移
                if(sum>0){
                    while(i<j && num[j]==num[--j]  );    //这里，跳过重复值直至遇到新值
                }else if(sum<0){
                    while(i<j && num[i]==num[++i] );     //这里，跳过重复值直至遇到新值
                }else{    //这里必然是sum=0 的位置
                    res.add(new ArrayList<>(Arrays.asList(num[k],num[i],num[j])));     //Arrays的asList可以实现列表的形式
                    //  继续查找，直至i=j; 这里要同时实现++i和--j，如果只实现其中一个不符合，因为这时三数之和为0，
                    //其中一个数的缩小或增大必然导致sum不为0
                    while(i<j && num[i]==num[++i] );
                    while(i<j && num[j]==num[--j]  );
                }
            }
        }
        return res;
        
        
    }
}