题解 | 三数之和

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        //边界值判断，数组长度小于3的返回空
        int len = num.length;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(len<3) return res;
        //为了使用双指针方法，需要先对整个数组进行排序，方便指针移动比较大小
        //对数组排序
        Arrays.sort(num);
        //依次遍历num的每个元素，利用双指针
        for(int k=0;k<len-2;k++){
            int flag = 0;
            //因为升序排列，所以如果cur值大于0，则后面元素之和是不可能比它小的
            int cur = num[k];
            if(cur>0) return res;
            //如果当前cur值和前面的cur值重复，则跳过这个cur值
            for(int i=0;k>=1&&i<k;i++){
                if(cur==num[i]) {
                    flag=1;
                    break;
                }
            }
            if(flag==1) continue;
            int i = k+1;
            int j = len-1;
            while(i<j){
                if(cur+num[i]+num[j]>0){
                    j--;
                }
                else if(cur+num[i]+num[j]<0){
                    i++;
                }
                else{
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(cur);
                    temp.add(num[i]);
                    temp.add(num[j]);
                    res.add(temp);
                    //这里再判断两个指针是否也和前面重复
                    while(i<j && num[i+1]==num[i]) i++;
                    while(i<j && num[j-1]==num[j]) j--;
                    i++;
                    j--;
                }
            }
        }
        return res;
    }
}