题目:N 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.
样例:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解决思路:像这种有关联关系的输入输出,C解决的话要考虑用哈希,Python的话我们直接考虑用字典解决就可以了,遍历数组,并且保存在字典中,查找字典中是否有符合的数字若符合直接返回数组下标和字典的value。
代码:
class Solution(object): #这里我用Python解决
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict = {}
for i in xrange(len(nums)):
x = nums[i]
if target - x in dict:
return (dict[target - x],i)
dict[x] = i
知识点:
range和xrange的区别
>>> a = range(5)
>>> print type (a)
<type 'list'> #我们可以看出range生成的是一个list对象
>>> print range(5)[0] #从list列表中打印list[0]
0
>>> b = xrange(5)
>>> print type(b)
<type 'xrange'>
>>> print xrange(5)[0]#而xrange是一个xrange类型,不会直接生成一个list,而是在每次调用的时候返回其中的一个值,节省内存
0