LeetCode-高效制胜-两数之和

yfx

July 26, 2021

1107 views

One comment

1130 words

算法 C/C++ Python

<div class="tip share">请注意，本文编写于 1399 天前，最后修改于 1375 天前，其中某些信息可能已经过时。</div>

# Problem - [两数之和](https://leetcode-cn.com/problems/two-sum/)

## 方法一：哈希表

> 最明显的思路就是两重循环枚举所有数字求和判断是否与目标值相等。此思路的时间复杂度为$O(n^2)$，注意到每次需要查找`target - num`。是否能够快速的找到`target - num`？
>
> 故使用哈希表先存储所有的`num`枚举所有的`num`判断哈希表中是否存在`target - num`即可，哈希表查找元素时间复杂度为$O(1)$。

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-d52d3c5fc8c2c47686b749c2137ee58b290' role="tab" data-target='#tabs-d52d3c5fc8c2c47686b749c2137ee58b290'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-4d71945e880847795fd9fcaec34ccd75331' role="tab" data-target='#tabs-4d71945e880847795fd9fcaec34ccd75331'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-d52d3c5fc8c2c47686b749c2137ee58b290' class="tab-pane fade active in">

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); ++ i) {
            auto it = mp.find(target - nums[i]);
            if (it != mp.end())
                return {it -> second, i};
            mp[nums[i]] = i;
        }
        return {};
    }
};
```

</div><div role="tabpanel" id='tabs-4d71945e880847795fd9fcaec34ccd75331' class="tab-pane fade  ">

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mp = dict()
        for i, num in enumerate(nums):
            if target - num in mp:
                return [mp[target - num], i]
            mp[num] = i
```

~~ps：加强python语法的学习！~~

</div>
</div>
</div>

### 复杂度分析：

* 时间复杂度：$O(N)$，对于每一个元素 `x`，我们可以$O(1)$地寻找到`tartget - x`。
* 空间复杂度：$O(N)$，哈希表的开销。

Last modification：August 18, 2021