求满足多约束的带索引输出两数之和问题的最优算法

核心思路 #

• 采用unordered_map<int, vector<int>>作为哈希表结构，键存储数组元素值，值存储该元素所有已遍历到的下标列表，天然支持重复元素的索引记录需求
• 单次遍历数组：每遍历到下标i的元素，先计算补数complement = T - nums[i]，若补数存在于哈希表中，将补数对应的所有下标依次与i配对，因为哈希表中存储的都是下标小于i的元素，天然满足小索引在前的规则，无需额外顺序判断
• 所有配对完成后仅需对结果列表做一次排序即可满足升序输出要求，整体时间复杂度为O(n + klogk)，k为符合条件的索引对总数，远优于原实现的O(n²)复杂度

原有代码问题说明 #

• SIGABRT越界错误：原代码未处理find函数找不到匹配元素的场景，find返回res2.end()时，减去res2.begin()得到的索引等于数组长度，直接访问res2[ti]会触发数组越界，导致内存错误
• 超时问题：每次匹配到补数后都全量遍历数组查找对应元素，额外引入O(n)开销，完全浪费了哈希表的O(1)查询特性
• 重复元素不兼容问题：unordered_set仅能存储唯一值，同一个元素重复出现时无法记录全部索引，自然无法处理重复元素场景

可直接运行的正确实现 #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void twoSum(const vector<int>& nums, int T) {
    unordered_map<int, vector<int>> value_indices;
    vector<pair<int, int>> result;

    for (int i = 0; i < nums.size(); ++i) {
        int complement = T - nums[i];
        // C++17以下版本可将contains替换为count(complement) > 0
        if (value_indices.contains(complement)) {
            for (int pre_idx : value_indices[complement]) {
                result.emplace_back(pre_idx, i);
            }
        }
        value_indices[nums[i]].push_back(i);
    }

    if (result.empty()) {
        cout << "-1 -1" << endl;
        return;
    }

    sort(result.begin(), result.end());
    for (auto& p : result) {
        cout << p.first << " " << p.second << endl;
    }
}

内容的提问来源于stack exchange，提问作者SacredMechanic