15. 三数之和[medium]

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[
  [-1, 0, 1],
  [-1, -1, 2]
]

通过次数229,777 提交次数845,068

Second Try

2020-06-05

参考题解进行改进的。使用左边点进行移动，一是方便在大于0的时候直接跳出，二是方便使用传说中的双指针。难点在于去除冗余值的细节：

双指针移动过程中，如果出现匹配的数值，默认情况两个指针该怎么移动？
双指针移动过程中，匹配数值接下来出现重复值，该怎么处理？
考虑完双指针移动的重复问题，在左边点移动过程中出现重复其实也会导致出现重复值。没想到一个这么经典的问题，也这么多坑。当然暴力解法是最容易的，但可能过不去。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums = sorted(nums)
        rv = []
        for i in range(len(nums)-2):
            if nums[i] > 0:
                break
            # remove redundant from left for the second occurance
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            m = i + 1
            r = len(nums) - 1
            while m < r:
                s = nums[i] + nums[m] + nums[r]
                if s == 0:
                    rv.append([nums[i], nums[m], nums[r]]) 
                    # remove redundant, 移除明显可处理的重复值
                    while (m + 1 < r)  and nums[m+1] == nums[m]:
                        m += 1
                    while (r - 1 > m) and nums[r-1] == nums[r]:
                        r -= 1
                    # remove redundant again
                    # 如果只移动一边，新的成立的数据肯定跟上一个存在重复               
                    m += 1
                    r -= 1
                elif s > 0:
                    r -= 1
                else:
                    m += 1
        return rv

执行用时 :400 ms, 在所有 Python 提交中击败了90.72%的用户
内存消耗 :18.2 MB, 在所有 Python 提交中击败了5.26%的用户

First Try

太惨了，排名倒数5%。

第一次试验先进行排序看能不能利用二分法之类，后来考虑使用中间点进行移动，不停选择两边的点，其实这样的效果明显没有使用左边点高效。其次对于冗余值直接使用python的set来处理，日常代码没问题，这里空间占用比较大。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []

        rv = []
        nums = sorted(nums)
        for i in range(1, len(nums)-1):
            right_col = set(nums[i+1: len(nums)])
            for j in range(i):
                s = nums[j] + nums[i]
                if -s in right_col:
                    rv.append((nums[j], nums[i], -s))
        rv = list(set(rv))
        return rv

执行用时 :1880 ms, 在所有 Python 提交中击败了5.63%的用户
内存消耗 :411.5 MB, 在所有 Python 提交中击败了5.26%的用户

15. 三数之和[medium]​

Second Try​

First Try​

15. 三数之和[medium]

Second Try

First Try