LeetCode 第1题:Two Sum

题目

给出一个整数数组,找出其中的两个整数,使相加等于指定整数,并返回这两个整数的索引。

假设每组输入只有一种解法,并且不能重复使用同一个元素。

举例:

给出 nums = [2, 7, 11, 15], target = 9,
因为 nums[0] + nums[1] = 2 + 7 = 9,
所以返回 [0, 1].

思路

最简单也是最直接的想法就是两重循环直接遍历计算就能得到结果,时间复杂度为 \O(n^2)。
但这肯定不是最优解。

题目中提到只会有一种解法,那就意味着不会有重复的整数,不然就会有多解。
既然没有重复的,那用一个哈希来存储数据就最合适了,整数为键,索引为值。
那我们要找两个整数的索引就很方便了,在遍历数组的时候,检查和目标的差值是否在哈希中,有的话就是答案了。

Go 实现

func twoSum(nums []int, target int) []int {
 h := make(map[int]int)
 for i, value := range nums {
 if wanted, ok := h[value]; ok {
 return []int{wanted, i}
 } else {
 h[target-value] = i
 }
 }
 return nil
}

运行时间:4ms,超过100%的 golang 提交。

Python3 重写

class Solution:
 def twoSum(self, nums, target):
 """
 :type nums: List[int]
 :type target: int
 :rtype: List[int]
 """
 h = {}
 for i, value in enumerate(nums):
 if value in h:
 return [h[value], i]
 else:
 h[target - value] = i
 return None

运行时间:52ms,超过47.04%的 python3 提交。

Python3 优化

从上面的数据上看效率有点低,应该是 enumerate 生成迭代器效率稍差,所以换用 range(len(...)) 的写法。

class Solution:
 def twoSum(self, nums, target):
 """
 :type nums: List[int]
 :type target: int
 :rtype: List[int]
 """
 h = {}
 for i in range(len(nums)):
 value = nums[i]
 if value in h:
 return [h[value], i]
 else:
 h[target - value] = i
 return None

运行时间:36ms,超过99.71%的 python3 提交。

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传