Leetcode: Three sum
Given a list of integers, add three integers at the same time so that the sum of those integers is
0. There should be no repetition of integers, for example
[-1, 0, 1] is equivalent to
[-1, 1, 0].
The solution makes use of the fact that duplicate numbers can be ignored. To do this, the numbers need to be sorted first. Then, if the next number is the same as the previous, it can be skipped. This does not affect the number of the other pointers, thus there can be the same number in different pointers.
In total there are two loops needed. The outer loop iterates from the smallest to the third-largest number. For every iteration, a pointer
p3 are defined. The pointer
p2 starts directly one position right of
p3 starts at the end of the list.
We then need to distinguish three cases. If the sum is exactly
0, we can add the item to the results. If it is greater than
0, we move the pointer
p3 to the left which makes the number smaller. If it is less than
0, we move
p2 to the right which increases the total sum. We continue this approach until
p3 meet, then continue with the outer iteration. Additionally, there is some logic to deal with duplicates.
Runtime: 1340 ms, faster than 50.64% of Python3 online submissions for 3Sum. Memory Usage: 18.2 MB, less than 39.78% of Python3 online submissions for 3Sum.