统计总和为K的子数组数量：滑动窗口代码失效原因及解决咨询

问题背景 #

你实现统计总和等于K的子数组数量功能时，编写了基于滑动窗口的C++代码，多数测试场景有效，但在数组{-1, -1, 1}、K=0的用例中失效。你尝试添加额外循环调整滑动窗口，但问题仍未解决，需要明确调整无效的原因及正确解法。

原始滑动窗口代码 #

int subarraySum(vector<int>& nums, int k)
{
    int start, end, curr_sum = 0, count = 0;

    start = 0, end = 0;
    while (end < (int)nums.size())
    {
        curr_sum = curr_sum + nums[end];
        end++;

        while (start < end && curr_sum >= k)
        {
            if (curr_sum == k)
                count++;
            curr_sum = curr_sum - nums[start];
            start++;
        }
    }
    return count;
}

调整后的滑动窗口代码 #

int subarraySum(vector<int>& nums, int k)
{
    int start, end, curr_sum = 0, count = 0;

    start = 0, end = 0;
    while (end < (int)nums.size())
    {
        curr_sum = curr_sum + nums[end];
        end++;

        while (start < end && curr_sum >= k)
        {
            if (curr_sum == k)
                count++;
            curr_sum = curr_sum - nums[start];
            start++;
        }
    }

    while (start < end)
    {
        if (curr_sum == k)
            count++;
        curr_sum = curr_sum - nums[start];
        start++;
    }
    return count;
}

调整无效的核心原因 #

滑动窗口的双指针收缩逻辑只适用于数组元素全为非负数的场景，依赖的是「窗口扩大时总和递增、窗口收缩时总和递减」的单调性，但你的数组包含负数，直接打破了这个前提：

• 当窗口内加入负数时，总和会变小；
• 当窗口移除负数时，总和会变大。

以测试用例{-1, -1, 1}、K=0为例：

1. 遍历到第二个元素时，curr_sum = -2，此时curr_sum >= 0不成立，内层收缩循环完全不执行，无法检查中间可能的子数组；
2. 遍历到第三个元素时，curr_sum = -1，同样不满足curr_sum >=0的条件，内层循环还是不执行；
3. 你添加的额外循环只是在遍历结束后继续收缩左指针，但此时curr_sum的变化逻辑依然不覆盖负数场景下的所有可能，只能碰巧统计到一个符合条件的子数组，但本质逻辑还是错误的，遇到其他带负数的场景（比如{1,-1,0}、K=0）依然会统计错误。

正确解法：前缀和+哈希表 #

针对包含负数的数组，必须使用前缀结合哈希表的方法，核心思路是利用前缀和的差值来判断子数组是否符合条件：

• 定义preSum[i]为数组前i个元素的总和，那么子数组nums[j..i-1]的总和等于preSum[i] - preSum[j]；
• 若preSum[i] - preSum[j] = k，则该子数组符合条件，我们只需要统计每个preSum[i] - k出现的次数，就能得到以i结尾的符合条件的子数组数量。

实现代码 #

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

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1; // 初始化前缀和为0的情况，处理从数组开头到当前位置总和为k的场景
    int preSum = 0;
    int count = 0;

    for (int num : nums) {
        preSum += num;
        // 检查是否存在前缀和等于preSum - k，存在则累加对应次数
        if (prefixCount.find(preSum - k) != prefixCount.end()) {
            count += prefixCount[preSum - k];
        }
        // 更新当前前缀和的出现次数
        prefixCount[preSum]++;
    }
    return count;
}

代码说明 #

• 初始化prefixCount[0] = 1：处理数组前i个元素总和正好等于k的情况，此时preSum[i] - k = 0，对应的次数为1；
• 遍历数组时，不断累加前缀和，每次检查preSum - k是否在哈希表中，若存在则将对应次数加到统计结果中；
• 最后更新哈希表中当前前缀和的出现次数，为后续元素的检查做准备。

以测试用例{-1, -1, 1}、K=0为例：

1. 初始preSum=0，prefixCount={0:1}；
2. 遍历第一个元素-1：preSum=-1，preSum - 0 = -1不在哈希表中，prefixCount[-1] = 1；
3. 遍历第二个元素-1：preSum=-2，preSum -0 = -2不在哈希表中，prefixCount[-2] =1；
4. 遍历第三个元素1：preSum=-1，preSum -0 = -1在哈希表中，次数为1，count +=1，之后prefixCount[-1]更新为2；
5. 最终返回count=1，符合预期。

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