15. 3Sum

Description:

Solution:

We need to nums.sort() before moving pointer.

i is a count, a is the value (enumerate)

 

if i > 0 and a == nums[i-1] => if i is bigger than 0, we make sure not using same value

l, r pointers to find the two sum for 0 of three sum.

 

Since we sort the values, if threeSum is bigger than 0, we should move r pointer to left.

elif threeSum is smaller than 0, we should move l pointer to right.

else threeSum is 0, then we are gonna find more combinations.

 

Also, be careful while nums[l] == nums[l-1] and 1 < r: => move again if the values are duplicated.

 

Time Complexity: O(nlogn) + O(n^2) = O(n^2)

Space Complexity: O(1) or O(N)