LeetCode之2sum,3sum

two-sum的问题是给你一个数组,一个target,在数组中找出两个数的和为target,最后返回这两个数的index。假设只有一组解(说明数组里没有重复的),而且不会使用同一个数字两次。


对于two-sum的解法最简单就是暴力求解,两层循环,时间复杂度是O(n2).还有更简单的方法是利用一个哈希表存储target-num,看nums中的num是否出现在哈希表中,如果出现,则找到结果。代码如下:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for i in range(len(nums)):
            if nums[i] not in map:
                map[target-nums[i]]=i
            else:
                return map[nums[i]],i


进阶的还有three-sum,找出数组nums中加和为0的三个数,只要利用two-sum的思想即可。注意nums中有重复的num,最后结果需要去重。主要说一下下面代码的去重方式,其实只要利用set()就可以达到去重的效果,可下面代码多了一句

if i>=1 and nums[i]==nums[i-1]:
                continue

这样提前判断条件,可以提前去掉一些重复的,相比于把去重工作全部交给集合set()去完成,这样能够减少代码运行时间,提高效率。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = set()
        nums.sort()
        for i in range(len(nums)-2):
            if i>=1 and nums[i]==nums[i-1]:
                continue
            maps = {}
            for j in range(i+1,len(nums)):
                if nums[j] not in maps:
                    maps[-nums[i]-nums[j]]=1
                else:
                    result.add((nums[i],nums[j],-nums[i]-nums[j]))
        return list(map(list,result))


评论

Live Sex Cams Free