LeetCode第一题 - 两数之和
Post

LeetCode第一题 - 两数之和

LeetCode 备忘。

题目

给定一个整数数组,找出和为指定值的两个元素的下标。举例说明:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

假设数组中有且只有一种组合可以得到正确答案,并且相同元素不可以重复使用。

解法一

很容易想到暴力破解,只要做两层循环就可以搜索出答案。实现起来和冒泡排序类似。

1
2
3
4
5
6
7
8
class Solution(object):
    def twoSum(self, nums, target):
        length = len(nums)
        for i in range(length):
            for j in range(i+1,length):
                if nums[i] + nums[j] == target:
                    return [i,j]
        

这个解法效率很低,运行2900ms,只打败了全球20%的玩家。

解法二

我们可以优化一下,用哈希表(字典)来保存数字的索引和值,这样搜索的复杂度就变成了O(1),而遍历的复杂度是N。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def twoSum(self, nums, target):
        length = len(nums)
        # 建立index和value的反向索引
        d = {x:i for i,x in enumerate(nums)}
        
        for i in range(length):
            part = target - nums[i] # 取差值
            if part in d and not d[part]==i: # 在字典中搜索差值
                return [i,d[part]]

提交看疗效,20ms,打败全球100%玩家。

解法三

其实还可以优化一下,这个哈希表可以延迟建立,这样可以省掉建表时的那次遍历。但效果嘛,不一定是优化,且看代码。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def twoSum(self, nums, target):
        length = len(nums)
        d = {} # 空字典
        
        for i in range(length):
            part = target - nums[i]
            if part in d:  # 检索字典,有则直接返回
                return [i,d[part]]
            else: # 没找到,加入字典
                d[nums[i]]=i

提交,也是20ms,依然打败100%全球玩家。不过要注意一点,这种算法返回的下标都是反的,比如上面两种算法返回的是[0,1],但是这里返回的就是[1,0]了。

2019年1月书单

关于吃的几个段子