Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution1
很容易想到循环遍历列表，复杂度为O(n2)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
Solution2
利用字典来实现，算法复杂度为O(n)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
map = {}
for i, a in enumerate(nums):
if target - a in map:
return [map[a], i]
map[target - a] = i
return -1, -1
反思
- 对于solution过程中需要用到下标的题目，enumerate通常比较实用
- map的查找效率为O(1)
- 两层循环可以利用map做cache将其简化，然后利用map的高效查找降低算法复杂度
- x + y = z的问题，变成了z - y = x的问题，其中z, y 为已知，x的查找转化成map的查找
