import java.util.*;
public class threeSum {
    public static void main(String[] args){
        int[] nums = new int[] {-2,0,1,1,2};
        threeSum obj = new threeSum();
        System.out.println(obj.threeSum(nums));
    }
    /* Approach: for loop + two sum
       Time: O(n^2)
       Space: O(1)
    * */
    private List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> result = new ArrayList();
        if(nums == null || nums.length < 3){
            return result;
        }
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            // 关键要想清楚，2SUM面对duplicate怎么办，3SUM面对duplicate怎么办
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            // two sum
            int lo = i + 1, hi = nums.length - 1;
            while(lo < hi){
                //consider duplicates
                //2 sum应对duplica
                if(nums[lo] + nums[hi] == 0 - nums[i]){
                    result.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                    while(lo < hi && nums[lo] == nums[lo+1]){
                        lo ++;
                    }
                    while(lo < hi && nums[hi] == nums[hi-1]){
                        hi --;
                    }
                    lo ++;
                    hi --;
                }else if(nums[lo] + nums[hi] < 0 - nums[i]){
                    lo ++;
                }else{
                    hi --;
                }
            }
        }
        return result;
    }
}