和为 K 的子数组 图解题解

这道题真正在问什么

题目给数组 nums 和整数 k，统计「连续子数组」——也就是一段下标相邻的元素——的和恰好等于 k 的个数。两个关键点：数组可能含负数，子数组之间可以重叠；要的只是个数，不需要返回具体位置。示例 nums = [1,2,3,-1,1,1,2,3]、k 取 3 时答案是 6，可见同一个位置可以同时属于多段答案。

为什么滑动窗口在这题会失效

很多人先想到滑动窗口：和小了扩右边、和大了缩左边。但窗口伸缩依赖一个前提——往里加数窗口和一定变大、往外扔数一定变小。数组一旦含负数，这个单调性就没了：扩窗可能让和变小，缩窗可能让和变大，指针不知道该往哪动。退回暴力做法「枚举每个起点、往后逐个累加」，时间是 O(n²)，数组一大就太慢。

子数组和为什么等于前缀和之差

关键观察：记前缀和 preSum 为从头累加到某个位置的总和，那么任意一段子数组的和，都等于「右端点处的前缀和」减「左端点前一位的前缀和」。于是「以当前位置结尾、和为 k 的子数组有几个」，等价于「更早的位置里，前缀和恰好等于 preSum - k 的有几个」。这一步把「枚举区间」翻译成「查一个确定的值出现过几次」，而后者正是哈希表 O(1) 能回答的——和两数之和里查 target - x 是同一招，只是把「值」换成了前缀和、把「下标」换成了出现次数。

解法随之成形：建一张表记录「前缀和的值 → 出现次数」，从左到右扫数组，每到一个数先累加出当前前缀和，查表里 preSum - k 出现过几次、答案就加几，然后把当前前缀和的计数加一，留给后面的位置查。

为什么要预置 0 出现 1 次、先查后存

表里一开始必须放一条「前缀和 0 出现 1 次」，它代表空前缀。少了它，「从下标 0 开始、整段恰好等于 k」的子数组会被漏数——这种情况下要查的 preSum - k 恰好等于 0，表里必须能查到。

循环体内先查 preSum - k、再把 preSum 存进表，顺序不能反。先存后查会把自己也当成候选：当 k 为 0 时 preSum - k 就等于 preSum 本身，先存就会查到自己、凭空多数一段长度为 0 的「子数组」。先查后存保证查到的永远是严格更早的前缀，对应的子数组长度至少为 1。

复杂度怎么算，还有哪些坑

时间 O(n)：每个数只做一次累加、一次查表、一次计数，均摊都是 O(1)。空间 O(n)：最坏时几乎所有不同的前缀和都要进表。另一个常见错误是往表里存前缀和出现的下标——本题只数个数，存「出现次数」就够了；存下标是「返回具体位置或最长长度」那类变体才需要的。如果题目改成「和能被 k 整除的子数组个数」，把哈希键换成前缀和对 k 取模的余数，同一套框架照用。

Python

def subarraySum(nums, k):
    from collections import defaultdict
    cnt = defaultdict(int)
    cnt[0] = 1               # 空前缀: 前缀和0出现1次
    preSum = ans = 0
    for x in nums:
        preSum += x
        ans += cnt[preSum - k]  # 查 need 出现几次
        cnt[preSum] += 1        # 再把当前前缀和存进去
    return ans

C++

int subarraySum(vector<int>& nums, int k){
    unordered_map<int,int> cnt;
    cnt[0] = 1;                       // 空前缀
    int preSum = 0, ans = 0;
    for(int x : nums){
        preSum += x;
        ans += cnt[preSum - k];      // 查 need 出现几次
        cnt[preSum] += 1;            // 存当前前缀和
    }
    return ans;
}

Java

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);                   // 空前缀: 前缀和0出现1次
    int preSum = 0, ans = 0;
    for (int x : nums) {
        preSum += x;
        ans += cnt.getOrDefault(preSum - k, 0); // 查 need
        cnt.merge(preSum, 1, Integer::sum);     // 存自己
    }
    return ans;
}