15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Code language: HTTP (http)

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Code language: HTTP (http)

Constraints:

• 3 <= nums.length <= 3000
• 105 <= nums[i] <= 105

本题第一想法就是可以简化成two sum。因为要nums[i] + nums[j] + nums[k] == 0 就必须要nums[j] + nums[k] == -nums[i]

因此我们可以把 -nums[i] 当成target，用一个twoSum的方法来找出nums[j] 和nums[k]

我们可以循环nums，把每一个-nums[i]当作target，然后对其利用twoSum。而twoSum计算时需要对target后面的所有index（j = i +1)进行计算，计算方式为：找到一个曾经出现过的nums[n] = target - nums[j]。

如果不存在，则说明这个数没有出现过，我们可以将 nums[j] 加入 HashMap，表示它已经被扫描过，等待后续元素与之配对。

如果有，那么(nums[j], -target(也就是nums[i]），target - nums[j])就是一组答案。

TwoSum需要的变量就是nums本身以及传进来的nums[i]的index（因为我们要从i+1开始找）

然后接下来我们要进行去重，对于某一个固定的nums[i] 我们必须避免nums[j]重复，不然会出现重复的答案组

因此在twoSum函数里我们要对nums[j]去重。

同时对于同样的nums[i]我们也需要去重。也就是在外循环里叫出twoSum的时候需要对nums[i]做一个重复判断。

去重虽然可以用set ()来做，但是会增加复杂度，再加上我们本身两次循环的时间复杂度已经达到了$O(n^2)$,完全可以用一个 $O(nlogn)$的sort()函数来先把nums排序，这样重复的数就会排在相邻位置，去重就方便了很多（判断nums[k] != nums[k+1]）

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res  = []
        for i in range(len(nums)):
            if nums[i] > 0:
                return res
            if i == 0 or nums[i -1 ] != nums[i]:
                self.twoSum(nums, i, res)
        return res
    
    def twoSum(self, nums:List[int], i:int, res:List[List[int]]):
        target = -nums[i]
        seen = set()
        j = i + 1
        while j < len(nums):
            com = target - nums[j]
            if com in seen:
                res.append([-target, nums[j], com])
                while j < len(nums) - 1 and nums[j] == nums[j + 1]:
                    j += 1
            seen.add(nums[j])
            j += 1

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res  = []
        for i in range(len(nums)):
            if nums[i] > 0:
                return res
            if i == 0 or nums[i -1 ] != nums[i]:
                self.twoSum(nums, i, res)
        return res
    
    def twoSum(self, nums:List[int], i:int, res:List[List[int]]):
        target = -nums[i]
        seen = set()
        j = i + 1
        while j < len(nums):
            com = target - nums[j]
            if com in seen:
                res.append([-target, nums[j], com])
                while j < len(nums) - 1 and nums[j] == nums[j + 1]:
                    j += 1
            seen.add(nums[j])
            j += 1