yicong@algo: ~/code/04-substring/0560-subarray-sum-equals-k.cpp

yicong@algo:~/code/04-substring$ cat 0560-subarray-sum-equals-k.cpp

560. 和为 K 的子数组

中等 子串 题目 ↗ 源码 ↗

// 思路

记 sumnums[i] = nums[0] + nums[1] + ... + nums[i-1],也就是"前 i 个数之和", 并规定 sumnums[0] = 0(前 0 个数之和)。 那么下标区间 [i, j-1] 的和 = sumnums[j] - sumnums[i]。 问题变成:数一数有多少对 (i, j) 满足 i < j 且 sumnums[j] - sumnums[i] == k。 版本一(你的写法):两层循环把所有 (i, j) 试一遍,O(n²)。 版本二:把等式变形一下 sumnums[j] - sumnums[i] == k → sumnums[i] == sumnums[j] - k 扫到 j 的时候,右边是已知的,左边是"历史上出现过的前缀和"。 于是只要一张哈希表记录"每个前缀和出现过几次",O(1) 就能查出来。 注意是"前面出现过几次",不是"有没有出现过"——所以要累加次数。

// 时间复杂度

版本一:O(n²),两层循环 版本二:O(n),每个元素扫一遍,哈希表查询均摊 O(1)

// 空间复杂度

版本一:O(n),前缀和数组 版本二:O(n),哈希表最多存 n+1 个不同的前缀和

// 易错点

1. sumnums 必须开到 n+1 个格子(下标 0 到 n),因为要能表示"空前缀"。 写成 vector<int> sumnums; 再 sumnums[0] = 0 是往空容器里写,直接崩。 2. 前缀和是累加:sumnums[i+1] = sumnums[i] + nums[i],不是 sumnums[i+1] = nums[i]。 3. 内层 j 必须从 i+1 开始。j <= i 会数出"反方向区间",凭空多计数。 4. 版本二的 count[0] = 1 这个哨兵不能漏,它代表"从下标 0 开始的子数组"。 5. 同一个前缀和会重复出现,哈希表里要累加次数,不能覆盖。 6. "先查表、后插入"的顺序不能反。反了的话 k == 0 时会把空子数组也数进去。 7. 这题的 nums[i] 可以是负数,前缀和不单调,所以不能用双指针 / 滑窗。

// 面试口述要点

1. 先给暴力:枚举所有子数组再求和的 O(n³),用前缀和降到 O(n²); 2. 再给变形:sumnums[j] - sumnums[i] == k ⟺ sumnums[i] == sumnums[j] - k, 右边已知、左边是历史记录,于是边扫边查哈希表,O(n); 3. 主动提负数的坑:有负数 → 前缀和不单调 → 双指针失效,但前缀和 + 哈希照常工作。

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = (int)nums.size();
        vector<int> sumnums(n+1,0);
        int ans = 0;

        for (int i = 0; i < n; i++)
            sumnums[i+1] = sumnums[i] + nums[i];   

        for (int i = 0; i <= n; i++)
            for (int j = i + 1; j <= n; j++) 
                if(sumnums[j] - sumnums[i] == k) ans++;

        return ans;
    }

    // ================================================================
    // 版本二:前缀和 + 哈希表,O(n)
    //   sumnums[j] - sumnums[i] == k  等价于  sumnums[i] == sumnums[j] - k
    //   扫到 j 时,只需要知道"前面有多少个下标 i 的前缀和等于 sum - k"
    //   count[sum] 记录前缀和 sum 已经出现过几次
    // ================================================================
    int subarraySum_v2(vector<int>& nums, int k) {
        // 前缀和 -> 它出现过几次
        // 哨兵:空前缀(前 0 个数之和)出现过 1 次,
        //       它对应"从下标 0 开始"的那些子数组
        unordered_map<int, int> count;
        count[0] = 1;

        int ans = 0;
        int sum = 0;                                 // 当前前缀和,等于 sumnums[j+1]

        for (int j = 0; j < (int)nums.size(); j++) {
            sum += nums[j];                          // 走到 j 为止的前缀和

            // ---------- 先查表 ----------
            // 前面每有一个下标 i 满足 sumnums[i] == sum - k,
            // 就对应一个以 j 结尾、和为 k 的子数组
            auto it = count.find(sum - k);
            if (it != count.end()) {
                ans += it->second;
            }

            // ---------- 后插入 ----------
            // 顺序不能反:先插入的话,k == 0 时会把"空子数组"自己数进去
            count[sum]++;
        }
        return ans;
    }
};

// 本地测试:输入 n k,然后 n 个整数;输出和为 k 的连续子数组个数
// 同时跑两个版本并比对结果,方便验证优化版和原版等价
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> nums(n);
    for (int& x : nums) cin >> x;

    int ans1 = Solution().subarraySum(nums, k);
    int ans2 = Solution().subarraySum_v2(nums, k);

    if (ans1 != ans2) {
        cout << "MISMATCH: v1=" << ans1 << " v2=" << ans2 << '\n';
        return 0;
    }
    cout << ans1 << '\n';
    return 0;
}