yicong@algo:~/code/01-hash$ cat 0001-two-sum.cpp
1. 两数之和
// 思路
一遍遍历,用 unordered_map 记录「已扫过的值 -> 下标」。 对每个 x,先查 target - x 是否已在表中,命中则返回 {它的下标, i}; 否则把 x 存入表中,留给后面的数配对。先查后插保证同一元素不被用两次。
// 时间复杂度
平均 O(n);最坏 O(n^2)(哈希冲突严重时退化)
// 空间复杂度
O(n)
// 易错点
1) 先插后查,target == 2x 时会返回 {i, i}(自己配自己) 2) 用 m[key] 判断 key 是否存在会插入默认值,必须用 count / find 3) 遍历 map 的写法需要额外判断 target - x != x
// 面试口述要点
暴力双重循环 O(n^2) -> 哈希表把「找搭档」降到平均 O(1); 一遍就够,因为配对是对称的;追问最坏情况时提哈希冲突与均摊 O(1)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < (int)nums.size(); ++i) {
int x = nums[i];
if (m.count(target - x)) return {m[target - x], i};
m[x] = i;
}
return {};
}
};
// 本地测试:输入 n target,然后 n 个整数;输出两个下标
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, target;
if (!(cin >> n >> target)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
vector<int> ans = Solution().twoSum(nums, target);
if (ans.size() == 2) cout << ans[0] << ' ' << ans[1] << '\n';
else cout << "no answer\n";
return 0;
}