分类：Array
考察知识点：Array(数组遍历) HashMap
最优解时间复杂度：O(n)
1. Two Sum
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].
这道题最优的解法就是创建一个HashMap,在Python中我们称为Dictionary(主要我用Python,更加习惯用Python来讲解内容),边遍历边存储原来的那些内容到一个Dictionary里供后面搜索。
还是拿[2,7,11,15]这个list举例：
| 遍历顺序 | index | old_dict | target-n是否在dict中 | new_dict |
|---|---|---|---|---|
| 2 | 0 | {} | N | {2:0} |
| 7 | 1 | {2:0} | 9-7=2,2在dict中，返回！ | |
| 11 | 2 | |||
| 15 | 3 |
代码：
最优解法:
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 确定边界
if len(nums)<2:
return [-1,-1]
# O(n)解法
num_dict={}
for i,n in enumerate(nums):
if (target-n) in num_dict:
return [num_dict[target-n],i]
else:
num_dict[n]=i
讨论：
1.这个题目我一开始是想用双循环去解的也就是一个循环套一个循环,感觉这个是最普通最大众的解法，但是时间复杂度太高了，为O(n^2)
2.后来我想过用另外一个方法去解也是一个循环,但是这个方法并不好，因为Python已经“暗中”遍历了好多遍了
for n in nums:
if (target-n) in nums:
#Python在这里暗中会遍历一遍
return [nums.index(target-n),nums.index(n)]
#这个index的函数也会让Python去暗中区遍历
3.另外上述方法不好的一个地方是，题目里讲了“may not use the same element twice”，如果要重新检测的话又要用到切片什么的就更加麻烦了。
WechatIMG1573.jpeg
最终我们交上第一题的完美答卷！Perfect Start!
