yicong@algo: ~/code/01-hash/0001-two-sum.cpp

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;
}