求向量中和为S的元素对数量及代码报错问题咨询

一、erase报错的原因 #

你用iter = m.erase(iter)报错的核心问题是循环逻辑和容器迭代器的行为冲突：

• 你的外层循环是for (auto iter = result.first; iter != result.second; iter ++)，每次循环结束会自动执行iter++
• 当调用erase(iter)时，函数会返回下一个有效的迭代器，但此时循环本身还会再执行一次iter++，相当于连续两次移动迭代器，直接跳过元素甚至访问失效迭代器，触发未定义行为
• 另外，equal_range返回的result.second是基于容器当前状态的，一旦删除元素，这个迭代器可能直接失效，导致iter != result.second的循环条件完全无效

二、更高效的解法 #

不需要用unordered_multimap存索引，改用哈希表统计已遍历元素的出现次数，就能做到平均O(n)时间复杂度，逻辑更简单高效：

long long CountSumS(vector<int>& a, int s) {
    long long cnt = 0;
    unordered_map<int, int> num_count; // 键：元素值，值：该元素已出现的次数

    for (int num : a) {
        int target = s - num;
        // 累加之前出现过的、能和当前元素组成sum的元素数量
        if (num_count.count(target)) {
            cnt += num_count[target];
        }
        // 当前元素加入哈希表，次数+1
        num_count[num]++;
    }
    return cnt;
}

解法逻辑说明 #

• 遍历数组时，每处理一个元素，先找能和它组成s的目标值在已经遍历过的元素里的出现次数——因为已遍历元素的索引都小于当前元素，天然满足i<j的条件
• 不需要存储索引，只统计元素出现次数，避免了索引判断的额外开销
• 哈希表的查找、插入操作平均时间复杂度都是O(1)，整体遍历一次数组即可完成统计

对比你原来的方法：原方法先插入所有元素，再逐个遍历对应范围，最坏情况下（比如所有元素相同）时间复杂度会退化为O(n²)，远不如这个解法高效。

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