LeetCode 两数之和、三数之和

旧城等待， 2022-04-13 05:42 212阅读 0赞

1.  两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

class Solution:
        def twoSum(self, nums, target):
            d = { }
            for i in range(len(nums)):
                x = target - nums[i]
                if x in d:
                    return [d[x],i]
                else:
                    d[nums[i]] = i

1.  三数之和

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

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

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

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

三个 for 硬着头皮干，实现了，但是果断超时

def threeSum1(self, nums):
            """ :type nums: List[int] :rtype: List[List[int]] """
    
            a = []
    
            n = len(nums)
    
            for  i in range(n):
                for j in range(n):
                    for k in range(n):
                        if  i != j  and j!= k  and i!=k  and nums[i] + nums[k] + nums[j] == 0:
                            if sorted([nums[i], nums[j], nums[k]]) not in a:
                                a.append( sorted([nums[i], nums[j], nums[k]]))
            return a
    
    
    # 超时 O（n3 * n㏒n）

求 `a+b = -c`，两个lops 加list存储 ，继续超时

def threeSum2(self, nums):
            """ :type nums: List[int] :rtype: List[List[int]] """
            ## nums = [-1,0,1,2,-1,-4]
            ## sort nums = [-4, -1, -1, 0, 1, 2]
            ## d = set([0, 1, 2, -4, -1])
            # 思路优化： 求 a+b = -c 即可
            n = len(nums)
    
            nums.sort()
    
            if n < 3 :
                return []
            d = { }
            res= []
            for di,dv in enumerate(nums):
                d[dv] = di
            for i1,v1 in enumerate(nums):
                for i2,v2 in enumerate(nums):
                    if -(v1 +v2)  in d   and i1 != i2 and  i1!= d[-(v1 +v2)] and i2 !=d[-(v1 +v2)]  :
                        if sorted([v1,v2,-(v1+v2)]) not  in res:
                            res.append(sorted([v1,v2,-(v1+v2)]))
    
            return res
    
    
    # 超时 O（n2 * n㏒n）

用set() 存储-c 这样 时间复杂度是 O（n2 \* O(1)），终于通过

def threeSum(self, nums):
            """ :type nums: List[int] :rtype: List[List[int]] """
    
            # 思路优化： 求 a+b = -c 即可
            nums.sort()
            res = set()
            for i,v in enumerate(nums[:-2]):
                if i>=1 and v == nums[i:-1]:
                    continue
                d = { }
                for x in nums[i+1:]:
                    if x not in d:
                        d[-v-x] =1
                    else:
                        res.add((v,-v-x,x))
            return map(list,res)
    
    
    # O（n2 * O(1)）