题解 | 三数之和

双指针

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        int n=num.length;
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(n<3){
            return res;
        }
        Arrays.sort(num);
        for(int i=0;i<n-2;i++){
            if(i!=0&&num[i]==num[i-1]){
                continue;
            }
            int left=i+1;
            int right=n-1;
            int target=-num[i];
            while(left<right){
                if(num[left]+num[right]==target){
                    ArrayList<Integer> temp=new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    while(left+1<right&&num[left]==num[left+1]){
                        left++;
                    }
                    while(right-1>left&&num[right]==num[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(num[left]+num[right]>target){
                    right--;
                }else{
                    left++;
                }
            }
        }

        return res;
    }
}