2026.7.2

1.和为K的子数组

任意连续子数组的和"转换成两个前缀和的差。遍历数组时维护当前前缀和 pre_sum，如果以前存在某个前缀和 x，满足 pre_sum - x = k，那么从那个前缀和之后到当前位置的连续子数组和就等于 k，因此只需要在哈希表中查找 pre_sum - k 是否出现过，并将其出现次数累加到答案中，最后再把当前前缀和加入哈希表，整个过程时间复杂度为 O(n)。

我最开始不理解为什么初始化要放 prefix = {0:1}，觉得它会干扰结果。实际上，它并不是多放了一个前缀和，而是为了统一处理从下标 0 开始的子数组**。如果不放 {0:1}，就必须额外写

if pre_sum == k: count += 1 来处理这种特殊情况；而放入 {0:1} 后，当 pre_sum == k 时，就会自动查找到 pre_sum - k = 0，程序自然会统计这类子数组，从而把特殊情况变成了普通情况。同时，哈希表中保存的是前缀和出现的次数，而不是前缀和值本身，因为同一个前缀和可能在多个位置出现，每出现一次，就意味着多了一个可以作为连续子数组起点的位置，因此需要把所有出现次数都累加到答案中。{0:1} 不会让答案变多，因为它从来没有创造新的子数组，刚开始初始化prefix = {0:1}只是把“从下标 0 开始的子数组”这一种情况，纳入了统一的哈希表统计方式。

2.最大子数组和--动态规划

可以把整个算法看成一个归纳证明：

初始情况：i = 0 时，只有一个子数组 [nums[0]]，所以 cur = nums[0]，定义成立。
归纳假设：假设处理到 i-1 时，cur 确实是以 nums[i-1] 结尾的最大连续子数组和。
归纳步骤：处理 i 时，所有以 nums[i] 结尾的子数组，要么是 [nums[i]]，要么是某个以 nums[i-1] 结尾的子数组再加上 nums[i]。根据上面的分析，只需要考虑其中最大的那个，也就是旧的 cur。因此：
cur = max(nums[i], cur + nums[i])

然后选最大的cur即可