# Leetcode 15. 3sum two pointers

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.