【LeetCode】0001两数之和

https://leetcode-cn.com/problems/two-sum

代码：

# -*- coding:utf-8 -*-
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        temp = [target - nums[i] for i in range(len(nums))]
        for i in range(len(nums)):
            flag = nums[i]
            for j in range(len(temp)):
                if temp[j] == flag and i != j:
                    return [i, j]
if __name__ == '__main__':
    nums = [2, 7, 11, 15]
    nums = [3, 2, 4]
    target = 6
    print(Solution().twoSum(nums, target))

思路：这道题我做的时候倒是没用什么具体的算法，只是利用一个辅助数组，其值为target – nums[i]，然后对比两个列表中是否有相同的元素，需要注意的就是第二层循环中的判断需要加 i != j 以防止自比较问题，第一次提交就是因为没有想到这个结果错了。

思考：但是我这里的对比列表用的是一个双层循环，这使得整个算法的时间复杂度上升到了n^2，查看评论后，对比可以换成字典，这样在字典中查找总的时间复杂度就会降到nlgn。

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    hashmap = {}
    for index, num in enumerate(nums):
        another_num = target - num
        if another_num in hashmap:
            return [hashmap[another_num], index]
        hashmap[num] = index
    return None