LeetCode第一题：两数之和

Ps：本系列文章只为记录自己刷LeetCode过程中的解题过程和思路。

题目来源，LeetCode

题目描述： 给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例： 给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解题过程和思路： 当我浏览了一便这个题目的时候，心里想，哇，通俗易懂，这不是超简单的嘛。emmm，题目意思是懂了，那么怎么用计算机解呢？首先映入我脑海中的是：emm，最基础的解法吧——暴力， 把数组所有可能的两数之和都求出来不就好了，但是这样子的做法时间复杂度是O(n^2)， emmm，实在不可取。接着，我又想呀想呀，怎么降低时间复杂度呢？ 排序怎么样？排序了之后从小到大遍历数组，算出每个数与后续数的和，由于排序过了，计算出来的求和结果将会是一个递增的序列，当求和结果大于目标值 target 之后便停止计算，接着遍历数组中第二个数。咦，好像可行，可以避免一些无用的求和计算。由于用了排序，因此时间复杂度在O(nlogn)与O(n^2)之间。博主太笨了，之后再想了许久也没想到更优的解法，因此参考了LeetCode上的大佬们的题解，哇，第一次感到世界如此奇妙。可以通过建立哈希表，也就是字典的方式来加快查询速度（空间换时间），具体怎么做呢？。将数组的值作为key，索引作为value建立字典，这样子如果我们对于数组中某个数num，要查找是否存在另外一个数another_num，使得两数之和为target，那怎么查找 another_num 这个数比较快呢？ 通过我们前面建立的字典，可以通过判断字典的keys里是否有another来查找，因此查找一般只需要O(1)时间（当没出现冲突的时候）。

解题收获： 字典的妙用——以空间换时间的方式加快查找效率，记好啦。

代码展示：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_d = {}
        for index,num in enumerate(nums): # 遍历nums数组枚举两个数中的第一个数
            another_num = target-num # 目标-第一个数求第二个数
            if another_num in nums_d: # 遍历nums_d字典判断两个数中的第二个数是否存在
                return min(index, nums_d[another_num]), max(index, nums_d[another_num]) # 若存在则返回
            else:
                nums_d[num] = index # 以num为两个数中的第一个数找不到答案，就将其放入存放第二个数的字典

结果展示：