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.

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.

Time complexity: O()

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.