LC560
和为 K 的子数组
前缀和 · 和为 K可视化:前缀和/积nums 连续子数组和=k 个数。
时间 O(n)空间 O(1)
题目1 / 11
题目与输入建立输入、目标与算法心智
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
正在加载算法场景...
当前发生了什么
nums 连续子数组和=k 个数。
机器状态
prefix sum、map 计数。
为什么正确
prefix map 存频次;ans+=map[prefix-k]。
不变量
map 记录前缀出现次数。
面试怎么说
前缀和+哈希 O(n)。
人类输入
nums 连续子数组和=k 个数。
机制
prefix map 存频次;ans+=map[prefix-k]。
机器状态
prefix sum、map 计数。
可观察结果
子数组个数。
不变量
- · map 记录前缀出现次数。
常见误区
- · prefix-k 出现几次就有几个子数组。
迁移练习
- · LC525 连续数组
- · LC974 整除
面试怎么答
前缀和+哈希 O(n)。