1. Two Sum 两数之和
难度: Easy
刷题内容
原题连接
- https://leetcode.com/problems/two-sum
- https://leetcode-cn.com/problems/two-sum
内容描述
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题方案
思路 1
我们在找两个的和是否等于某一个值。
如果是两两组合的笛卡尔积，相当于闭着眼碰运气，时间复杂度为: O(n^2)
例如:
* 2+7 2+11 2+15
* 7+11 7+15
* 11+15
思路 2
如果我们换一种方式: target - 当前数字, 需要的另外一个变量就变成已知！
- 通过字典(哈希 Hash)对nums建立词库表 loopup, 时间复杂度是 0(n)
- 判断差值是否存在 lookup 中, 时间复杂度是 0(1)
- 所以最后的结果就是: O(n) * O(1) = O(n)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
lookup = {}
for i, num in enumerate(nums):
if target - num in lookup:
# 为什么先后顺序是 lookup[target - num], i
# 因为当前是i，而差值只能从 lookup 中找，而 lookup 是在 i 之前面入库的
# 所以 顺序是 lookup[target - num], i
return [lookup[target - num],i]
lookup[num] = i
return []
if __name__ == "__main__":
nums = [2, 7, 11, 15]
target = 9
so = Solution()
n = so.twoSum(nums, target)
print("结果: ", n)
