vvrf / DSA.log

问题拆解

统计数组里有多少个连续子数组的和恰好等于 k。枚举所有子数组是 O(n^2) 个，逐个求和更慢；用前缀和能把“求任意子数组的和”降到 O(1)，但枚举左右端点仍是 O(n^2)。另外要注意数组里有负数，滑动窗口的单调性不成立，这条路走不通。

真正的突破口是把条件改写成前缀和的语言：记 prefix[i] 为前 i 个数的和，子数组 (j, i] 的和为 k，等价于 prefix[i] - prefix[j] = k，即 prefix[j] = prefix[i] - k。于是问题变成：扫到位置 i 时，前面有多少个前缀和等于 sum - k？这是个典型的“边扫边数”问题，拿哈希表记录每个前缀和出现的次数即可。

“子数组和等于 k”翻译成“两个前缀和相差 k”，配对计数就交给哈希表——这和两数之和是同一个动作：找互补值，边扫边存。

前缀和加哈希计数

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1); // 空前缀，让从下标 0 开始的子数组也能配上对
    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;
        ans += count.getOrDefault(sum - k, 0); // 前面每个 sum-k 都对应一个子数组
        count.merge(sum, 1, Integer::sum);
    }
    return ans;
}

def subarraySum(nums: List[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1  # 空前缀，让从下标 0 开始的子数组也能配上对
    total = ans = 0
    for x in nums:
        total += x
        ans += count[total - k]  # 前面每个 total-k 都对应一个子数组
        count[total] += 1
    return ans

func subarraySum(nums []int, k int) int {
    count := map[int]int{0: 1} // 空前缀，让从下标 0 开始的子数组也能配上对
    sum, ans := 0, 0
    for _, x := range nums {
        sum += x
        ans += count[sum-k] // 前面每个 sum-k 都对应一个子数组
        count[sum]++
    }
    return ans
}

pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    let mut count = std::collections::HashMap::new();
    count.insert(0, 1); // 空前缀，让从下标 0 开始的子数组也能配上对
    let (mut sum, mut ans) = (0, 0);
    for x in nums {
        sum += x;
        ans += count.get(&(sum - k)).copied().unwrap_or(0); // 前面每个 sum-k 都对应一个子数组
        count.entry(sum).and_modify(|c| *c += 1).or_insert(1);
    }
    ans
}

两处细节最容易翻车。第一是初始化 {0: 1}：它代表“空前缀”的和 0 出现过一次，没有它，所有从下标 0 开始、恰好和为 k 的子数组都会被漏数——比如 nums = [3], k = 3 会错误地返回 0。第二是先查再存的顺序：必须先用 sum - k 去查表、累加答案，再把当前 sum 存进去；反过来的话，当 k = 0 时当前前缀和会和自己配对，凭空多出一段长度为零的“子数组”。

复杂度

指标	复杂度	原因
时间	`O(n)`	一次遍历，哈希表读写均摊 O(1)
空间	`O(n)`	哈希表最多存 n+1 个不同的前缀和

可以迁移的模式

子数组的和、异或等区间量，都能改写成两个前缀量的关系，把区间问题变成配对问题；
“边扫边查互补值、再把自己入表”的顺序保证只和左侧配对，天然不重不漏；
哨兵条目（这里的 {0: 1}）对应“空前缀”，凡是配对可能顶到数组开头的场景都要想到它。

同一副骨架换个谓词就是新题：和被 k 整除（974）、连续数组（525）、路径总和 III（437），识别出“前缀 + 哈希配对”后它们全是一道题。