求目标和子数组数量的C++代码逻辑、功能及输出解析咨询

功能说明 #

这段C++代码用于统计无序整数数组中，和恰好等于给定目标值的连续子数组数量。子数组指数组中连续的元素序列，比如数组[1,2,3]的子数组包括[1]、[1,2]、[2]等。

核心思路：前缀和+哈希表优化 #

代码采用前缀和结合哈希表的方案，把时间复杂度从暴力枚举的O(n²)降到O(n)，效率大幅提升。核心逻辑是利用前缀和的差值快速定位符合条件的子数组。

重点代码片段解析 #

用户关注的这段代码是实现核心逻辑的关键：

if (prevSum.find(currsum - sum) != prevSum.end())
    res += (prevSum[currsum - sum]);

• 关键概念：
  • currsum：遍历到第i个元素时，从数组开头到当前元素的累计和（前缀和）。
  • prevSum：哈希表，键是之前出现过的前缀和，值是该前缀和出现的次数。
• 逻辑原理：
  如果存在某个前缀和prefix = currsum - sum，那么从prefix对应的位置的下一个元素到当前元素的子数组，其和必然等于currsum - prefix = sum。哈希表中记录的prefix出现次数，就是以当前元素结尾、和为目标值的子数组数量，直接加到结果计数器即可。

举个简单例子：假设当前前缀和是10，目标值是5，哈希表中记录前缀和5出现了2次，说明有2个不同的起始位置能和当前位置组成和为5的子数组，结果计数器直接加2。

完整代码逐行解析 #

#include<bits/stdc++.h>
using namespace std;

int cntSubarrays(vector<int>arr,int sum){
    // 哈希表：存储已遍历过的前缀和及其出现次数
    unordered_map<int, int> prevSum;
    int n = arr.size();
    // 结果计数器，记录符合条件的子数组总数
    int res = 0;
 
    // 当前累计的前缀和
    int currsum = 0;
 
    for (int i = 0; i < n; i++) {
        // 将当前元素加入前缀和，更新累计值
        currsum += arr[i];
 
        // 情况1：从数组开头到当前元素的和正好等于目标值，直接计数+1
        if (currsum == sum)
            res++;
 
        // 情况2：查找是否存在前缀和等于currsum - sum，存在则累加对应次数
        if (prevSum.find(currsum - sum) != prevSum.end())
            res += (prevSum[currsum - sum]);
 
        // 将当前前缀和存入哈希表，更新出现次数
        prevSum[currsum]++;
    }
 
    return res;
}

• unordered_map<int, int> prevSum：用哈希表存储已出现的前缀和，实现O(1)时间复杂度的查找，避免重复计算。
• 循环遍历数组的每一步：
  1. 更新当前前缀和currsum，把当前元素加入累计。
  2. 检查当前前缀和是否等于目标值：如果是，说明从数组开头到当前位置的子数组符合条件，结果+1。
  3. 查找哈希表中是否存在currsum - sum：如果存在，将对应次数加到结果中，这些次数就是以当前元素结尾的有效子数组数量。
  4. 将当前前缀和存入哈希表，更新该前缀和的出现次数。

示例验证 #

比如输入数组[1, 2, 3, -3, 1]，目标值sum=3：
遍历结束后返回结果4，对应的有效子数组分别是：[1,2]、[3]、[3,-3,1]、[2,3,-3,1]，与代码计算结果一致。

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