import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for(int i = 0; i < num.length - 2; i++){
            if(i > 0 && num[i] == num[i-1]) continue;
            int target = -num[i];
            int l = i+1,r = num.length - 1;
            while(l < r){
                if(num[l] + num[r] == target){
                    list.add(new ArrayList<Integer>(Arrays.asList(-target,num[l],num[r])));
                    l++; r--;
                    while(l < r && num[l] == num[l-1]) l++;
                    while(l < r && num[r] == num[r+1]) r--;
                }else if(num[l] + num[r] < target){
                    l++;
                }else {
                    r--;
                }
            }
        }
        return list;
    }
}