Two Sum（两数之和）哈希表解法原理

核心思想

使用 unordered_map 建立一个哈希表，保存已经遍历过的数字以及它对应的下标。

遍历数组时，对于当前数字 nums[i]：

• 计算它需要的另一个数字：

[
need = target - nums[i]
]

• 如果 need 已经存在于哈希表中，说明找到了两个数：

[
nums[i] + need = target
]

返回它们的下标。

• 如果不存在，则将当前数字和下标存入哈希表，供后续查找。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int> mp;

        for(int i = 0; i < nums.size(); i++)
        {
            int need = target - nums[i];

            if(mp.count(need))
            {
                return {mp[need], i};
            }

            mp[nums[i]] = i;
        }

        return {};
    }
};

哈希表存储内容

定义：

unordered_map<int,int> mp;

其中：

key   : 数组中的数字
value : 数字对应的下标

例如：

数组：

nums = [2,7,11,15]

遍历过程中哈希表：

2  -> 0
7  -> 1
11 -> 2
15 -> 3

执行过程示例

输入：

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

第一次遍历

当前：

nums[0] = 2

计算需要的数字：

need = 9 - 2 = 7

查看哈希表：

mp中不存在7

保存当前数字：

mp[2] = 0

哈希表：

2 -> 0

第二次遍历

当前：

nums[1] = 7

计算：

need = 9 - 7 = 2

查看哈希表：

mp中存在2

找到：

2对应下标0

返回：

{0,1}

因为：

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

每个元素只遍历一次：

• 插入哈希表：平均 O(1)
• 查找哈希表：平均 O(1)

因此：

时间复杂度：

O(n)

空间复杂度：

O(n)

算法流程

遍历数组

      |
      v

计算需要的数字 need = target - 当前数字

      |
      v

哈希表中查找 need

      |
      +----------------+
      |                |
    存在             不存在
      |                |
      v                v

返回两个下标       保存当前数字和下标