【leetcode】三数之和（3Sum）【python】AC解答

淡淡的烟草味﹌ 2022-05-08 02:40 110阅读 0赞

**题目链接：**[三数之和][Link 1]  
![在这里插入图片描述][70]  
利用和为0的性质，可以不用O(N^3)  
而使用O(N^2)来解决

class Solution:
        def isNotSame(self, lists, list):  # 判断是否重复函数
            for i in range(len(lists)):
                if list == lists[i]:
                    return False
            return True
        def threeSum(self, nums):
            lists = []
            for i, num1 in enumerate(nums):
                for j, num2 in enumerate(nums[i + 1:]):
                    num3 = (num1 + num2) * -1
                    if num3 in nums[i + j + 2:]:    #注意这里是i + j + 2因为j是从0开始的
                        list = [num1, num2, num3]
                        list.sort()
                        if self.isNotSame(lists, list):
                            lists.append(list)
            return lists
    nums = [-1, 0, 1, 2, -1, -4]
    print(Solution().threeSum(nums))

**需要注意的是代码中i + j + 2是怎么来的**  
但是这样做了之和，会有几个特别大的例子超时：  
![在这里插入图片描述][70 1]  
因此做了改进算法

1.  不用判断重复函数，不用list，而是使用集合set，最后再转为list，因为集合里面肯定没有重复元素，这样可以减少执行时间
2.  使用hashmap的思想，将nums中的重复元素去掉，变为set，再进行三数求和，最后只需要确保这三个数的个数小于hashmap的个数就行  
    ***使用了from collections import Counter，实际上返回了一个hashmap***

from collections import Counter
    nums = [0,0,1,1,2,3,3,4,4,4]
    cnt = Counter(nums)
    print(cnt)

输出：Counter({4: 3, 0: 2, 1: 2, 3: 2, 2: 1})

***AC代码***

from collections import Counter
    
    class Solution:
        def threeSum(self, nums):
            counts = Counter(nums)
            numSet = list(set(nums))
            result = set()#使用set可以防止重复
            for i, num1 in enumerate(numSet):
                #for j, num2 in enumerate(numSet[i:]):
                for j in range(i, len(numSet)):
                    num2 = numSet[j]
                    num3 = (num1 + num2) * -1
                    #if num3 in numSet[i + j:]:
                    if num3 in counts:
                        list1 = [num1, num2, num3]
                        Coun = Counter(list1)
                        shouldAdd = True
                        for num in Coun.keys():
                            if Coun[num] > counts[num]:  #比较是不是足够
                                shouldAdd = False
                        if shouldAdd:
                            result.add(tuple(sorted(list1)))   #足够
            return list(result)

[Link 1]: https://leetcode-cn.com/problems/3sum/description/
[70]: /images/20220508/952e5eeb7b084d3584b7b03512f3a6b9.png
[70 1]: /images/20220508/62ef2712b4fd412ea7770ca927c806e2.png