子数组的通用思考方式

一、枚举右端点

子数组问题: 枚举右端点^[1]

二、子数组+中位数+条件k (个数)

• 2488. 统计中位数为 K 的子数组 (前缀和 + 维护左、枚举右)

由于题目保证 $nums$ 中的整数互不相同

「$k$ 是长为奇数的子数组的中位数」等价于「子数组中小于 $k$ 的数的个数 = 大于 $k$ 的数的个数」

总和为 0、数量相等、轴对称、元素具有 01 二分性，就可以考虑分别给「0元素」「1元素」赋权值-1、1求和处理

Tip

准确的说是「个数」，能得到一个和个数有关的数学式子，就可以转换成 1（或者 -1），毕竟在讨论个数的时候，每个元素的贡献就是 1 了。

注解

[1]

来源: Dijkstra 最短路 单调栈【力扣双周赛 128】 的 Q4