两数之和，求目标值

题目：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
解题思路
求两数之和，使用快慢指针的方式，当两个指针 取出的函数值相加为目标值时，满足条件

第一种解法：暴力枚举

此种解法最容易想出来，但消耗内存过大

class Solution(object):
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        L = []
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    L.append(i)
                    L.append(j)
                j = j + 1
            i = i + 1
        return L

双重for循环：双指针进行便利求和
时间复杂度：n*n，空间复杂度，引入了一个新的数组，为n

代码改造

class Solution(object):
    def twoSum(self, nums, target):
        # 方法1. 便利数组，枚举法，时间和空间消耗极大
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

时间复杂度：n*n，空间复杂度：1

方法二：哈希表

函数方法：
便利字典中所有键值对的方法：

for...in... # 循环语句去便利所有键值对

==enumerate()==函数使用说明：

• enumerate()是python的内置函数
• enumerate在字典上是枚举、列举的意思
• 对于一个可迭代的（iterable）/可遍历的对象（如列表、字符串），enumerate将其组成一个索引序列，利用它可以同时获得索引和值
• enumerate多用于在for循环中得到计数

# 例如：输出列表中每个字符对应的下标
listx = ["这", "是", "一个", "测试"]
for i in range(len(listx)):
	print i, listx[i]
# enumerate()函数的使用
listx = ["这", "是", "一个", "测试"]
for index, item in enumerate(listx):
    print index, item

输出结果如下:

故本题可用哈希表进行修改：
思路分析：
通过哈希表可以减少列表中查找的时间

class Solution(object):
    def twoSum(self, nums, target):
        # 方法二：哈希表,set没有index，dict没有add属性
        visited = dict()
        for i,num in enumerate(nums):
            if (target-num) in visited:
                return (visited[target-num], i)
            visited[nums[i]] = i
        return []

错误分析：
- 使用set，但是set()不能返回下标，故采用dict()
时间复杂度：o(N),空间复杂度o(1)