Readme

2488.Count-Subarrays-With-Median-K

考虑以k为median的subarray定义，就是在比k大的元素和比k小的元素一样多。这就说明我们其实并不关心nums的具体数值，所以一个常见的技巧是将原数组转化为-1,0,1三种元素，分别代表小于、等于和大于k的分布。

对于以k为median的subarray，我们容易发现，如果该subarray长度是奇数，那么其中的元素之和必然是0. 如果该subarray长度是偶数，那么其中的元素之和必然是1. 所以我们其实就是寻找有多少个元素和是0、长度为奇数的subarray（记做A），以及多少个元素和是1、长度为偶数的subarray（记做B）。

对于这类subarray sum的题目，使用前缀和是必然的套路。假设截止到i的前缀和是sum，且该前缀的长度是偶数，那么我们只需要找出：有多少前缀和是sum、长度为奇数的前缀，两个前缀之差就代表了A；有多少前缀和是sum-1、长度为偶数的前缀，两个前缀之差就代表了B。

同理，假设截止到i的前缀和是sum，且该前缀的长度是奇数，那么我们只需要找出：有多少前缀和是sum-1、长度为奇数的前缀，两个前缀之差就代表了B；有多少前缀和是sum、长度为偶数的前缀，两个前缀之差就代表了A。

所以我们需要维护两个Hash表。evenSum[s]表示前缀和是s、且长度是偶数的前缀有多少个；oddSum[s]表示前缀和是s、且长度是奇数的前缀有多少个。我们遍历每个元素i，根据上面的方法计算有多少个以i为结尾的、符合条件的subarray（A类型或B类型），然后再更新oddSum或者evenSum，一路走下去。

PS：这个思路类似于LC 525.