57. 3Sum

a + b = -c, 3Sum reduces to 2Sum problem.
[c, a, b]

* Handling Duplicates in 2Sum

Say index s and e are forming a solution in a sorted array. Now givens nums[s], there is a unique nums[e] such that nums[s] + nums[e] == Target. Therefore, if nums[s+1] is the same as nums[s], then searching in range s+1 to e will give us a duplicate solution. Thus we must move s till nums[s + 1] != nums[s] to avoid getting duplicates.

while s < e and A[s] == A[s + 1]:  # s, 正在处理的.
  s = s + 1

* Handling Duplicates in 3Sum.

Imagine we are at index i and we have invoked the 2Sum problem from index i+1 to end of the array. Now once the 2Sum terminates, we will have a list of all triplets which include nums[i]. To avoid duplicates, we must skip all nums[i] where nums[i] == nums[i - 1].

if i > 0 and nums[i] == nums[i - 1]: # i - 1, 已经处理的.
  continue

外循环, 去重.
a + b = -c, c = nums[i] 的两两组合已经全部求过, 所以跳过后边和 nums[i] 相等的数.

class Solution:
    def threeSum(self, A):
        # init
        A.sort()
        n = len(A)
        res = []
        # -5, -5, -5, 2, 3, 10
        i = 0
        while i < n - 2 and A[i] <= 0:
            while i > 0 and i < n - 2 and A[i] == A[i - 1]:
                i += 1
            c = A[i]
            l, r = i + 1, n - 1
            while l < r:
                if A[r] + A[l] > -c:
                    r -= 1
                elif A[r] + A[l] < -c:
                    l += 1
                else:
                    res.append((c, A[l], A[r]))
                    while l < r and A[l] == A[l + 1]:
                        l += 1
                    l += 1
                    r -= 1
            i += 1
        return res