LeetCode Hot 100 | 10. 和为k的子数组

原理推导

定义

设数组为 nums，我们需要找到子数组 nums[j...i]，使得其和为 k。

定义 前缀和 pre[i] 为从数组开头到索引 i 的元素之和：

$pre[i] = nums[0] + nums[1] + ... + nums[i]$

公式变换

任意一段子数组 nums[j...i] 的和可以表示为两个前缀和的差：

$Sum(j, i) = pre[i] - pre[j-1]$

题目要求子数组和为 k，即：

$pre[i] - pre[j-1] = k$

我们通常遍历数组，当前的 pre[i] 是已知的。我们需要寻找是否存在一个过去的 pre[j-1] 满足上述条件。因此，移项得到核心公式：

$\mathbf{pre[j-1] = pre[i] - k}$

结论

在遍历到第 i 个元素时，如果哈希表中存在 key 为 pre[i] - k 的记录，说明之前出现过某个前缀和，把它减去后，剩下的部分和正好是 k。

核心疑问解答：为什么要找 `pre - k`？

很多初学者会误以为应该找 k，这是混淆了"前缀和"与"子数组和"。

当前手里拿的：pre[i] (从头加到现在的总和，比如 10)。
目标想要的：k (中间一段子数组的和，比如 4)。
需要切掉的：为了得到 4，必须把头部多余的那段切掉。多余的那段长度就是 10 - 4 = 6。
操作：去哈希表里查，"以前有没有出现过和为 6 的前缀？"
- 如果有，说明我们可以从那个位置"剪断"，剩下的就是我们要的 k。

图解逻辑：

索引:      0   ...   j-1   j   ...   i
数组:     [A,  B,  C,  D,  E,  F,  G]
          |_____________| |_________|
             前缀和 X        目标子数组 k
          |_________________________|
                   当前前缀和 pre

          pre - X = k  ==>  X = pre - k

代码实现

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 记录最终结果（符合条件的子数组个数）
        int result = 0;
        
        // 记录当前遍历到的位置的前缀和
        int pre = 0;
        
        // 哈希表：
        // Key   : 前缀和的值
        // Value : 这个前缀和出现的次数
        unordered_map<int, int> umap;
        
        // 【关键初始化】
        // 意义：代表前缀和为 0 出现了一次。
        // 作用：如果某个子数组是从头开始的（nums[0...i] == k），
        // 那么 pre - k = 0。我们需要在 map 里找到这个 0，否则会漏掉从头开始的情况。
        umap[0] = 1;

        for (const int& num : nums) {
            // 1. 更新当前前缀和
            pre += num;

            // 2. 核心判断：检查历史记录中是否存在一个前缀和 X，
            //    使得 pre - X = k (即 X = pre - k)
            if (umap.find(pre - k) != umap.end()) {
                // 如果存在，说明找到了符合条件的子数组。
                // 累加的次数是 umap[pre-k]，因为可能前面有多种组合都能得到那个前缀和。
                result += umap[pre - k];
            }

            // 3. 将当前的前缀和记录到哈希表中
            // 注意：一定要先判断（第2步），再记录（第3步）。
            // 否则如果 k=0，会把自己刚算出的 pre 算进去，导致错误。
            umap[pre]++;
        }

        return result;
    }
};

复杂度分析

时间复杂度: $O(N)$ $O (N)$
- 我们只需要遍历数组一次。
- 哈希表的查找和插入操作平均是 $O(1)$ 的。
空间复杂度: $O(N)$ $O (N)$
- 最坏情况下（例如数组全是正数），所有前缀和都不同，哈希表需要存储 $N$ 个元素。

复习重点

初始化陷阱：永远不要忘记 umap[0] = 1。
- 记忆口诀：如果不加这行，就找不到"从下标 0 开始的"那些子数组。
顺序问题：先 查 后 存。
- 先检查 umap.find(pre - k)，再执行 umap[pre]++。这是为了避免子数组长度为 0 的逻辑错误（虽然本题没有长度限制，但逻辑上是"用过去的前缀和"，不能用现在的自己减自己）。
Value 的含义：
- Map 的 value 存的是次数，而不是索引。因为题目问的是"有多少个"，而不是"在哪儿"。如果是问"最长子数组长度"，value 就应该存索引。