15. 3Sum

Description

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solutions

1. 暴力-Two Sum 的解法

　　之前作为 Two Sum 的题目，用哈希表或者集合来存查找的数，于是将 Three Sum 通过固定一个数值的方式转换成 Two Sum 的题目求解，结果 TLE 了。

from typing import List
import collections
# Time: O(n^2)
# Space: O(n)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        n = len(nums)
        res = []
        for i in range(n):
            two = self.twoSum(nums[:i]+nums[i+1:], -nums[i])
            for j in range(len(two)):
                add = [nums[i]]+two[j]
                add.sort()
                if add not in res:
                    res.append(add)
        return res

    def twoSum(self, nums, target):
        if not nums:
            return []
        n = len(nums)
        visited = set()
        res = []
        for i in range(n):
            if target-nums[i] in visited:
                res.append([target-nums[i], nums[i]])
            else:
                visited.add(nums[i])
        return res

2. 排序+双指针

　　可以先将数组排序，然后从左到右遍历每一个数，在这个数右边使用双指针从两边往中间选两个数，看加和是否合乎要求，如果不是就按照跟目标数值的大小关系，动态调整左右指针。

# Time: O(n^2)
# Space: O(n)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) <= 2:
            return []
        n = len(nums)
        res = []
        nums.sort()
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i + 1, n - 1
            while l < r:
                _sum = nums[l] + nums[i] + nums[r]
                if _sum == 0:
                    res.append([nums[l], nums[i], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                    while l < r and nums[r] == nums[r+1]:
                        r -= 1
                elif _sum < 0:
                    l += 1
                else:
                    r -= 1
        return res
# 313/313 cases passed (960 ms)
# Your runtime beats 55.05 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.2 MB)

References

15. 3Sum