C++ 第39题：std::unordered_set 实现 O(1) 两数之和判定（Two Sum 原型）

题目

编写程序，解决经典算法问题“两数之和”（Two Sum）。给定一个无序整数数组和一个目标值 target，使用 std::unordered_set 作为高效记忆化哈希表，通过一次线性遍历，判定数组中是否存在两个不同索引的元素之和恰好等于 target。时间复杂度严格为 O(N)，空间复杂度为 O(N)。

输入格式：无需外部输入（内置测试数组与两组 target）。

输出格式：若存在输出配对成功的两个具体数字，若不存在输出无解提示。

数据范围与约定：数组长度 <code>N ≤ 10^5</code>。

思路与算法

1. 暴力双循环 O(N^2) 的淘汰
双层嵌套循环枚举每一对数字会超时；利用空间换时间思想，使用哈希集合在 O(1) 检索“与当前元素互补的差值”。

2. 一次遍历边查边存
遍历到元素 x 时，先在集合中查是否存在 target - x：若已存在则直接命中成功；若不存在则将 x 插入集合，继续向后遍历。该模式还能自然规避“同一个元素自身相加两次”的典型逻辑漏洞。

3. 数值溢出防御
两数相加可能发生整型溢出，求差值时应选用范围充足的 long long 进行计算。

完整程序

#include <iostream>
#include <vector>
#include <unordered_set>
#include <sstream>

bool findTwoSum(const std::vector<int>& nums, int target, int& outA, int& outB) {
    std::unordered_set<int> visited;

    for (int num : nums) {
        int complement = target - num;
        if (visited.find(complement) != visited.end()) {
            outA = complement;
            outB = num;
            return true;
        }
        visited.insert(num);
    }

    return false;
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15, -2, 8};
    int target = 9;

    std::cout << "测试数组: { 2, 7, 11, 15, -2, 8 }, 目标和 target: " << target << "\n";

    int a = 0, b = 0;
    if (findTwoSum(nums, target, a, b)) {
        std::cout << "【成功匹配】找到两数: " << a << " + " << b << " = " << target << "\n";
    } else {
        std::cout << "【未找到】不存在两数之和等于目标值\n";
    }

    // 第二轮测试
    target = 100;
    if (findTwoSum(nums, target, a, b)) {
        std::cout << "【成功匹配】找到两数: " << a << " + " << b << " = " << target << "\n";
    } else {
        std::cout << "测试 target = 100 结论: 不存在两数相加为 100\n";
    }

    return 0;
}

运行示例

输出：

测试数组: { 2, 7, 11, 15, -2, 8 }, 目标和 target: 9
【成功匹配】找到两数: 2 + 7 = 9
测试 target = 100 结论: 不存在两数相加为 100