背景介绍
在四月份面阿里实习生的时候，面试官曾经给过建议是多刷一些编程题，因为本人计算机基础相对薄弱，自己的实验室环境并不太注意代码效率， 很抱歉一直拖到了现在才开始。笔者使用python进行编程实现，题目主要来自 leetcode.
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].
问题解析
题目给定一个list和一个int, 需要使用list当中的两个element求和得到int, 然后返回这两个element的index即可。
初步思路：
- target由两个不同的int组成，这两个int不可能同时等于 target / 2，所以必然存在其中一个大于 target / 2， 而另外一个小于 target / 2；
- 这两个int的和等于target，找到其中一个，就等于是确定了另外一个的值；
代码实现
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i, x in enumerate(nums):
if x <= target / 2:
y_hat = target - x
try:
for j , y in enumerate(nums):
if y == y_hat and i != j:
return [j, i]
except ValueError:
continue
return None
按照我的想法，实现了一个\(O(n^2)\)的方法，简单的在小于 \( target / 2 \)的数字 x 中进行遍历，找到有相应的 y 满足
结合leetcode给出的solution，采用hash可以有效的降低时间复杂度，尤其是在遍历的时候，可以将 \( O(n) \) 变为 \( O(1) \)，代码如下：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 将列表转换为用hash实现的dict
hash_nums = dict()
for i, x in enumerate(nums):
hash_nums[x] = i
# 寻找另外一个符合要求的点的位置
for i, x in enumerate(nums):
com = target-x
if com in hash_nums and i != hash_nums[com]:
return [i, hash_nums[com]]
return None
上面这段代码是有两个循环，可以进一步缩小到一个循环：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hash_nums = dict()
for i, x in enumerate(nums):
com = target-x
if com in hash_nums and i != hash_nums[com]:
return [i, hash_nums[com]]
hash_nums[x] = i
return None
其他技能
range 和 xrange 的区别
这两个都是用来做循环的，区别在于range在实现的时候是创建好一个包含所有元素的list，而xrange则会返回一个生成器，每用一个则生成一个，不会占用太多内存，
所以会快一些；
但是在python3当中，已经取消了xrange，将range改成了python2当中的xrange。
python dict
python 的 dict 是通过hash的方式实现的，可以大大缩短遍历时间。