每天(?)一道Leetcode(1) 3Sum

Array

015. 3Sum

Given an array nums of n integers, are there elements in nums such that ? Find all unique triplets in the array which gives the sum of zero.
即：
找到数组中的子集，这些子集满足：
1.长度为3
2.元素相加为0
3.unique

Solutions

首先想到的最蠢的方法，利用三个for循环取出所有元素个数为的子集，并判断他们的和是否为，若为并且之前不存在中，就加入

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        A=[]
        n=len(nums)
        for i in range(n-2):
            for j in range(i+1,n-1):
                for k in range(j+1,n):
                    if nums[i]+nums[j]+nums[k]==0:
                        s=sorted([nums[i],nums[j],nums[k]])
                        if s not in A:
                            A.append(s)
                        
        return A

时间复杂度为，所以结果很显然：Time Limit Exceeded

然后想办法去掉一个循环，降低时间复杂度

def threeSum2(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        d = collections.Counter(nums)     
        nums_2 = [x[0] for x in d.items() if x[1] > 1]  ##重复元素
        nums_new = sorted([x[0] for x in d.items()])  ##所有(唯一)元素排序
        rtn = [[0, 0, 0]] if d[0] >= 3 else []
        for i, j in enumerate(nums_new):
            if j <= 0:
                numss2 = nums_new[i + 1:]
                for y in numss2::
                    if 0 - j - y in [j, y] and 0 - j - y in nums_2: ### 三个元素中有两个相等
                        if sorted([j, y, 0 - j - y]) not in rtn:
                            rtn.append(sorted([j, y, 0 - j - y]))
                    if 0 - j - y not in [j, y] and 0 - j - y in nums_new:  ###三个元素各不相同
                        if sorted([j, y, 0 - j - y]) not in rtn:
                            rtn.append(sorted([j, y, 0 - j - y]))
        return rtn

这个答案同样Time Limit Exceeded，虽然这个答案时间复杂度也很大，但是可以学习使用 collections，常用的有collections.defaultdict()和collections.Counter()

参考一个用while循环的方法

    def threeSum3(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort() ##排序 
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1  ##固定i时，指定两个指针，用来遍历数组元素
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l +=1    ##s<0说明nums[l]过小，应该换大一点，所以后移
                elif s > 0:
                    r -= 1  ##s<0说明nums[r]过大，应该换小一点，所以前移
                else:
                    res.append((nums[i], 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
                    l += 1; r -= 1  
        return res