LeetCode子数组和为k解法疑问：结果不符及前缀和计数困惑

测试用例结果的正确性验证 #

你提到的测试用例[-3,6,-3,6,-3]、k=3，解法返回5是正确的，所有符合条件的子数组如下：

• 索引0-1：[-3, 6]，和为3
• 索引1-2：[6, -3]，和为3
• 索引2-3：[-3, 6]，和为3
• 索引3-4：[6, -3]，和为3
• 索引0-4：[-3,6,-3,6,-3]，和为-3+6-3+6-3=3

你觉得Map中key=0的计数为2导致结果异常，其实这是合理的：当遍历到最后一个元素时，当前前缀和是3，curr - k = 0，此时Map里key=0出现了2次——一次是初始的空数组前缀和0，另一次是遍历到第三个元素后的前缀和0。这两次分别对应子数组0-4（从开头到末尾）和3-4（最后两个元素），这两个都是有效的子数组，所以这部分的计数是正确的，并没有异常。

为什么要统计所有前缀和的出现次数 #

这个解法的核心逻辑是利用前缀和的差值找符合条件的子数组：
我们定义prefix[i]为数组前i个元素的和（prefix[0]=0，对应空数组的和），那么子数组nums[j...i-1]的和就等于prefix[i] - prefix[j]。我们需要这个差值等于k，也就是prefix[i] - prefix[j] = k，转换一下就是prefix[j] = prefix[i] - k。

所以对于每个当前的前缀和prefix[i]，我们需要知道之前已经出现过多少次prefix[j] = prefix[i]-k——每一次这样的出现，都对应一个符合条件的子数组。如果只关注和为k的情况（比如只统计prefix[i]=k），那只能找到从数组开头到当前位置的子数组，会漏掉所有中间起始的子数组（比如nums[j...i-1]中j>0的情况）。

尤其是当数组包含负数时，前缀和会重复出现，统计每个前缀和的出现次数，才能准确算出所有满足prefix[j] = prefix[i]-k的j的数量，从而得到所有符合条件的子数组个数。

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