LC930
和相同的二元子数组
前缀和 · 二元子数组可视化:前缀和/积nums 全 0/1,子数组和=goal 个数。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
正在加载算法场景...
当前发生了什么
nums 全 0/1,子数组和=goal 个数。
机器状态
prefix、map。
为什么正确
同 LC560:prefix 计数 map,加 map[prefix-goal]。
不变量
0/1 数组 prefix 递增? 0/1 仍可计数。
面试怎么说
前缀和+map O(n)。
人类输入
nums 全 0/1,子数组和=goal 个数。
机制
同 LC560:prefix 计数 map,加 map[prefix-goal]。
机器状态
prefix、map。
可观察结果
和为 goal 的子数组个数。
不变量
- · 0/1 数组 prefix 递增? 0/1 仍可计数。
常见误区
- · 与 560 同模板。
迁移练习
- · LC560
- · LC974
面试怎么答
前缀和+map O(n)。