一类关于统计满足特定条件的连续子数组数量的题目,如连续子数组的和为k,最大/小值在范围内等等。

枚举直觉是直接枚举所有子数组, 复杂度,可以通过优化左端点选取来切入。

关注以下两点:

  • 右端点唯一性,任一连续子数组都有唯一的结束位置(右端点),故可以固定右端点来思考,统计以该点作为右端点的子数组数量
  • 条件的延续性,即什么情况下可以用到之前计算过的状态,什么情况下要归零

相关题目:

题目简介
795 区间子数组个数子数组最大值在 [left,right] 的个数
202503141758 930 和相同的二元子数组