leetcode - 三数之和2

leetcode: 三数之和（补充：昨天搞考试去了）

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

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

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

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

n个整数找到所有的a + b + c = 0，二话不说，我们先遍历试试

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        rnums = []
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] == 0:
                        flag = 1
                        for a in rnums:
                            if a == [nums[i], nums[j], nums[k]]:
                                flag = 0
                                break
                        if flag:
                            rnums.append([nums[i], nums[j], nums[k]])

        return rnums;

嗯，不愧是我，直接超时

好的，我们再想想其他办法= =

发现一个问题，如果前面的数相加已经超过0，那么第三个数就不用继续判断，就可以省下一部分速度，这也是一种剪枝了

class Solution(object):

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums = sorted(nums)
        rnums = []
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] > 0:
                    break
                for k in range(j+1, len(nums)):
                    if nums[i] + nums[j] + nums[k] > 0:
                        break
                    if nums[i] + nums[j] + nums[k] == 0:
                        flag = 1
                        for a in rnums:
                            if a == [nums[i], nums[j], nums[k]]:
                                flag = 0
                                break
                        if flag:
                            rnums.append([nums[i], nums[j], nums[k]])

        return rnums;

发现确实速度上是快一些，从290个测试用例走到了311个测试用例，那么还有什么优化方法呢，发现我之前的查重方法是遍历已找到的三数组，那么现在我试着从循环时判断

class Solution(object):

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        rnums = []
        for i in range(len(nums)):
            if i == 0 or nums[i] > nums[i-1]:
                if nums[i] > 0:
                    break
                for j in range(i+1, len(nums)):
                    if j == i+1 or nums[j] > nums[j-1]:
                        if nums[i] + nums[j] > 0:
                            break
                        for k in range(j+1, len(nums)):
                            if k == j+1 or nums[k] > nums[k-1]:
                                if nums[i] + nums[j] + nums[k] < 0:
                                    continue
                                elif nums[i] + nums[j] + nums[k] == 0:
                                    rnums.append([nums[i], nums[j], nums[k]])
                                    break

        return rnums;

好的 ，明显快一些，但是311用例明显是我的一生之敌（要不然把311用例算出来然后if掉算了= =||玩笑），既然是两层遍历那就把后两层遍历用左右的双指针法减少遍历次数吧，发现双指针法。。。真TM好用，连去重都自动做好了

class Solution(object):

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        rnums = []
        for i in range(len(nums)):
            if i == 0 or nums[i] > nums[i-1]:
                l = i + 1
                r = len(nums) - 1
                while l < r:
                    s = nums[i] + nums[l] + nums[r]
                    if s == 0:
                        rnums.append([nums[i], nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while r > l and nums[r] == nums[r+1]:
                            r -= 1
                    elif s > 0:
                        r -= 1
                    else:
                        l += 1

        return rnums;

双指针大法好！

无论遇到什么困难，都不要害怕，奥利给！🍺