JunyiCode
3/22/2020 - 3:35 AM

15. 3Sum

2 pointers

/*
tricky part: 
  1. skip equal elements to avoid duplicate
    1.1 first element duplicates
    1.2 second and third element duplicate


The idea is to sort an input array and then run through all indices of a possible first element of a triplet. 
For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. 
Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.
*/




class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 3) return res;
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; i++) {
            if(nums[i] > 0)
                break;   //optimization
            if(i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
                int low = i + 1, high = nums.length - 1, target = 0 - nums[i];
                while(low < high) {
                    if(nums[low] + nums[high] == target) {
                        res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while(low < high && nums[low] == nums[low + 1])   low++;
                        while(low < high && nums[high] == nums[high - 1]) high--;
                        low++;
                        high--;
                    } else if(nums[low] + nums[high] < target) {
                        low++;
                    } else {
                        high--;
                    }                
                }
            }       
        }
        return res;
    }
    
    // public int[] twoSum(int[] nums, int target) {
    //     int[] res = new int[2];
    //     Map<Integer, Integer> map = new HashMap<>();
        
    //     for(int i = 0; i < nums.length; i++) {
    //         if(map.containsKey(target - nums[i])) {
    //             res[0] = map.get(target - nums[i]);
    //             res[1] = i;
    //             return res;
    //         }
    //         map.put(nums[i], i);
    //     }
        
    //     return res;
    // }
}