一类关于统计满足特定条件的连续子数组数量的题目,如连续子数组的和为k,最大/小值在范围内等等。
枚举直觉是直接枚举所有子数组, 复杂度,可以通过优化左端点选取来切入。
关注以下两点:
- 右端点唯一性,任一连续子数组都有唯一的结束位置(右端点),故可以固定右端点来思考,统计以该点作为右端点的子数组数量
- 条件的延续性,即什么情况下可以用到之前计算过的状态,什么情况下要归零
相关题目:
题目 | 简介 |
---|---|
795 区间子数组个数 | 子数组最大值在 [left,right] 的个数 |
202503141758 930 和相同的二元子数组 |