# LeetCode-Two Sum
Date: 2021-05-10


#### **问题**

Given an array of integers `nums` and an integer `target`, return _indices of the two numbers such that they add up to `target`_.

You may assume that each input would have **_exactly_ one solution**, and you may not use the _same_ element twice.

You can return the answer in any order.

 

**Example 1:**

**Input:**

```
 nums = [2,7,11,15], target = 9

```

**Output:**

```
 [0,1]

```

**Output:**

```
 Because nums[0] + nums[1] == 9, we return [0, 1].

```

**Example 2:**

**Input:**

```
 nums = [3,2,4], target = 6

```

**Output:**

```
 [1,2]

```

**Example 3:**

**Input:**

```
 nums = [3,3], target = 6

```

**Output:**

```
 [0,1]

```

 

**Constraints:**

- `2 <= nums.length <= 10`3
- `-10`9 `<= nums[i] <= 10`9
- `-10`9 `<= target <= 10`9
- **Only one valid answer exists.**

 

#### **解答：**

创建一个字典，以值为key，value为值具体的索引信息， 因为**_exactly_ one solution ，**所以可以不考虑等值的情况，遍历列表判断，target-当前值，是否存在字典中。 也就是判断当前值与之前所有值（存放在字典中）是否满足和为指定值target的。

```
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
      dict = {}     
      for index, value in enumerate(nums):
        remaining = target-value
        if remaining in dict:
          return [dict[remaining], index]
        dict[value] = index
      return []
         
                

```

时间复杂度O(n), 遍历列表时间为n， 查询字典时间复杂度O(1)

空间复杂度O(n), 最坏的情况下需要在字典中存放所有的数值。

 

#### **参考及引用**

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

Photo by **[Frank Cone](https://www.pexels.com/@frank-cone-140140?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)** from **[Pexels](https://www.pexels.com/photo/lightning-strikes-2258536/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)**