题目

来源：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.

示例：
(1) nums=[2, 7, 9, 11], target=9 -> [0, 1]
(2) nums=[2, 5, 5, 7], target=10 -> [1, 2]
(3) nums=[2, 4, 5], target=4 -> [] （注意：不是[0, 0]，因为相同的元素只能使用一次）

解题思路及代码

解法一

作为LeetCode鼻祖题目，这道题的难易度是简单。但是第一次做LeetCode，之前也没有认真学过数据结构，所以很自然的就会想到用两个for循环进行暴力求解，这样复杂度就为O(n²)

def twoSum(nums, target):
　　for i in range(len(nums)):
　　　　nn = target - nums[i]
　　for j in range(i + 1, len(nums)):
　　　　if nums[j] == nn:
　　　　return [i, j]
　　return []

输出

[1,2]
[0,1]
[]

解法二

如果仅仅是用暴力求解，那这道题就没有意义了，所以应该考虑降低复杂度，用空间换取时间。再回过头来看题目，nums是list，需要返回的是索引，因此可以很自然的想到哈希，而在python中，字典dict就是一个很典型的hash结构，利用hash查找的复杂度为O(1)，这样就有可能只用一个for循环，也就是O(n)来实现。

class Solution:
    def twoSum(nums, target):
        nums_dict = {}
        for n, val in enumerate(nums):
            nn = target - val
            if nn in nums_dict:
                return [n, nums_dict[nn]]
            nums_dict[val] = n
        return []


s = Solution()
print(s.twoSum([2, 4, 4, 7], 10))
print(s.twoSum([2, 7, 9, 11], 9))
print(s.twoSum([2, 4, 5], 4))                    

输出

[2, 1]
[1, 0]
[]

LeetCode 1. two num

原文：https://www.cnblogs.com/wareteng/p/12100445.html