Leetcode 15. 3sum two pointers

Question

The solution do not allow duplicate triplets, we can sort the input array, so the duplicated values will be next to each other, it will be easy for us to skip the duplicate ones.

input array: nums = [-1,0,1,2,-1,-4]
sort input array: nums = [-4,-1,-1,0,1,2]

We will iterate through the array, and find the other two pairs of the current value nums[i] using two pointers. One pointer low starts at the index i+1 after the current index i, and the other pointer high starts at the end of the array. Since the array is sorted, if the sum of low and high is larger than -nums[i], we move high to the left to decrease the sum, so it will closer to -nums[i]. If the sum of low and high is smaller than -nums[i], we move low to the right to increase the sum. If we find a match, and it is not duplicated, we will add it to the result. We will check the rest of the array until low is equal to high (low and high are both indexes), then we move on to check for pairs for the next element in the array.

• check empty array and array length less than 3
• if nums[i] is larger than 0, not need to check for pairs, just return the result. Since the array is sorted, if nums[i] is larger than 0, the rest of the array are all larger than 0, the sum of the triplets will not be 0.
• Check for duplicates: (1) if current nums[i] is the same as nums[i-1], the number we are looking for pairs have already been checked (it is duplicated). We should move to nums[i+n] where nums[i+n]!==nums[i-1], then check pairs for nums[i+n]. (2) if we find match, but nums[lo]===nums[lo+1]&&nums[hi]===nums[hi-1] the pair for nums[i] are duplicated. We move lo to the right and hi to the left, until they are not duplicated.

Code with explanation

var threeSum = function(nums) {
    //when nums is empty or length less than 3, return []
    if(nums===[] || nums.length < 3) return []
    //sort the input array
    nums.sort((a,b)=>a-b)
    
    let res = []
    //since we have at least 2 pointers, we only need to check until         //the third last element
    for(let i=0; i< nums.length-2; i++){
    //the array is sorted, when nums[i]>0, the rest of the array are //all larger than 0, the sum of the triplets cannot be 0
        if(nums[i] > 0) break
        
        //skip value that has already been paired
         while(i>0&&i< nums.length-2 && nums[i]===nums[i-1]){
            i++
         }
        
        //set two pointers
        let lo = i+1
        let hi = nums.length-1
        
        //keep check for pairs until lo>=hi 
            while(lo<hi){
                if(nums[lo]+nums[hi]>0-nums[i]){
                    hi--
                    
                }else if(nums[lo]+nums[hi]<0-nums[i]){
                    lo++
                   
                }else{ //find match pair    
                    res.push([nums[i],nums[lo],nums[hi]]) 
                    
//check the next low and high pointer pair to see if they are the //same pair. If they are, move both until the next pair is not //duplicated
                    while(lo<hi&&nums[lo]===nums[lo+1]&&nums[hi]===nums[hi-1]){
                        lo++
                        hi--
                    } 
                    
                    lo++
                    hi--
                }
            }
        }            
    return res 
};

Time complexity: O(n²)

Space complexity:from O(logn) to O(n), depending on the implementation of the sorting algorithm. For the purpose of complexity analysis, we ignore the memory required for the output.