LeetCode-Hot100-两数之和

梦开始的地方，有人相爱，有人在深夜开车去看海，有人LeetCode第一题做不出来。今天就开始更新LeetCode热题100这个模块。首先就是第一道，两数之和，刚开始学习的话，它看似困难，实则一点不简单hhh。

题目

看到题目很多同学第一想法应该是暴力枚举，这种当然是最直接的做法。

这种做法即双重循环，外层固定一个数，内层遍历剩余部分，检查两数之和是否等于 target。

但显然这种方法的时间复杂度是 O(n²) 这个时间复杂度是很高的，同时题目中也问了我们是否可以想出一个时间复杂度小于 O(n²) 的算法。

那么需要我们对上述做法进行改进，内层查找本质上是“线性查找”，每次都需要遍历剩余部分。如果能把“查找 target - nums[i]”这一步从 O(n) 降到 O(1)，整体时间就能降到 O(n)。

哈希表——O(1)查找的索引工具

哈希表 / 字典
一种基于键值对的数据结构，通过哈希函数将键映射到存储位置，实现平均O(1)的插入、删除和查找操作。

那本题的正解就是哈希表，在本题中的具体用法体现如下：

键（key）：数组中已经遍历过的数字num[i]。
值（value）：该数字对应的下标i。

我们只需要回答一个问题：“某个数之前出现过吗？如果出现过，它在哪个下标？”

哈希表恰好提供了这种能力。

补充：哈希表本质上是一个数组，通过一个哈希函数 hash(key) % array.length 来决定 key 的存放位置。理想情况下不同的 key 对应不同的槽位，查找时只需计算一次哈希地址就能直接获取到 value。
哈希冲突可通过链地址法解决。
工程上负载因子控制得当，平均复杂度仍为 O(1)。
综上就是哈希表能在绝大多数情况下提供 O(1) 查找性能的核心原因。

需要我们注意的是不能一开始就把所有元素全部存入哈希表。如果先全存进去，再遍历每个元素时查询 target - nums[i]，那么当 target = 10，nums = {5, 5} 时，遍历第一个 5，查询到第二个 5（已经在表中），会错误地返回 [0,0]（同一个元素使用两次）。正确的做法是边遍历边插入，确保当前元素不参与自己的查找。

哈希表 vs 数组下标法：如果数组的值范围非常小且已知，可以用数组代替哈希表（如 value→index 映射），但本题值域不限，哈希表是通用解法。

一次线性扫描的遍历和更新过程

算法的核心是只做一次循环，在每次循环中先查询哈希表中是否存在 target - nums[i]，若存在则立即返回；若不存在，则将当前 (nums[i], i) 存入哈希表，然后继续。

设想你正在玩一个配对游戏：每走到一个新数字时，你就回头看看之前走过的数字里有没有能和你配对的。如果你每走一步之前先把当前数字记下来，那么未来任何数字回头看你时都能找到你。
“查”必须在“存”之前，保证当前数字只与“过去”的数字配对。
避免与“现在”或“未来”的数字配对，防止重复使用同一元素。

唯一解假设的影响：题目保证“只有唯一一组解”，这意味着我们不需要考虑冲突（比如多个不同位置的数都能配对）。因此一旦找到就可以立即返回，代码更简洁。

Code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> pos;
        for(int i=0;i<nums.size();i++)
        {
            int need=target-nums[i];
            if(pos.count(need)) return {pos[need],i};
            else pos[nums[i]]=i;
        }
        return {};
    }
};

趣味评论小剧场

人生就像这道两数之和：
你带着自己的「目标」出发，一开始往哈希表里张望时，空空如也，难免会慌，以为全世界都找不到和自己凑齐圆满的那一位。
可你别急着否定、也不用回头重走一遍老路。
你只管往前走，把自己安安稳稳地放进岁月里。
你以为你在寻找另一半，
其实后面的那个人，也正循着同一份目标向你走来。
等他出现时，你早已在他的「哈希表」里等候多时，
他一回头，就刚好对上你。
最好的契合从不是单方面的穷追猛找，
而是你沉淀自己，她奔赴而来，
时间一到，自然凑成恰好的圆满。