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即可