15. 3Sum

Loading...LeetCode

感觉如果没做过2Sum那一堆题目，即便是明确知道要用双指针的情况下，这题也不容易。我先去把2Sum的题基本都做了，再回来做的这道。

思路可以看作先固定一个数字之后执行 167. Two Sum II - Input array is sorted， 但是有个去重问题不好解决，先用set配合map函数在最后做了去重，但很慢。研究了一下在过程里去重也可以（line 7, 15, 16），就是思考的时候比较绕。

set + map

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []
        nums.sort()
        res = set()
        for i, n in enumerate(nums[:-2]):
            l, r = i+1, len(nums)-1
            while l < r:
                cur = n + nums[l] + nums[r]
                if cur > 0: r-=1
                elif cur < 0: l+=1
                else:
                    res.add((n, nums[l], nums[r]))
                    r -= 1
                    l += 1
        return map(list, res)

过程中去重

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []
        nums.sort()
        res = []
        for i, n in enumerate(nums[:-2]):
            if i > 0 and n == nums[i-1]: continue
            l, r = i+1, len(nums)-1
            while l < r:
                cur = n + nums[l] + nums[r]
                if cur > 0: r-=1
                elif cur < 0: l+=1
                else:
                    res.append([n, nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]: l+=1
                    while l < r and nums[r] == nums[r-1]: r-=1
                    r -= 1
                    l += 1
        return res

12/29/2020 Update

如果要求不对 nums 进行 sort，如何解答？

本还是仍然是先固定一个元素，然后在剩下的里面找 2sum，但因为不 sorted 了，要以其他方式去重。即直接找 c，对每个候选 c 进行判断，0-a-c 是否存在于候选 b 中，是则记录解，不是就把该候选 c 当作候选b。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n, res = len(nums), []
        if n < 3: return res
        
        A = set()
        for i in range(n-2):
            if nums[i] not in A:
                diff = -nums[i]
                B, C = set(), set()
                for j in range(i+1, n):
                    if nums[j] not in A and nums[j] not in C:
                        if diff - nums[j] in B:
                            res.append([nums[i], diff-nums[j], nums[j]])
                            C.add(nums[j])
                        else:
                            B.add(nums[j])
                A.add(nums[i])
                
        return res