难度: Hard
给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。
注意：
[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。示例 1：
输入：nums = [3,2,1,4,5], k = 4 输出：3 解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
示例 2：
输入：nums = [2,3,1], k = 3 输出：1 解释：[3] 是唯一一个中位数等于 3 的子数组。
提示：
n == nums.length1 <= n <= 1051 <= nums[i], k <= nnums 中的整数互不相同运行时间: 69 ms
内存: 27.0 MB
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
count = [0] * (n + 1)
count[0] = 1
d = 0
p = nums.index(k)
for i in reversed(range(p)):
d += 1 if nums[i] > k else -1
count[d] += 1
res = count[0] + count[1]
d = 0
for i in range(p + 1, n):
d += 1 if nums[i] < k else -1
res += count[d] + count[d+1]
return res
这个题解使用了一种基于平衡计数的策略来高效地统计子数组。首先，找出中位数 k 在数组中的位置 p。然后，从 p 向左扫描，使用 d 来统计当前位置到 p 的平衡状态（大于 k 的元素增加 d，小于 k 的元素减少 d），并在 count 数组中记录每个 d 值出现的次数。接着，从位置 p+1 向右扫描，更新 d 的值，并利用之前记录在 count 数组中的平衡状态来统计符合条件的子数组数量，这是基于左侧的平衡状态可以与右侧的平衡状态结合，形成以 k 为中位数的子数组。最终，通过对所有可能的平衡状态进行统计，得到以 k 为中位数的所有子数组的数量。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
count = [0] * (n + 1) # 用于记录每个平衡值 d 的出现次数
count[0] = 1 # 初始状态，没有元素时平衡值为0
d = 0
p = nums.index(k) # 找到 k 的索引位置
# 从 k 的位置向左扫描，更新平衡值 d 和 count 数组
for i in reversed(range(p)):
d += 1 if nums[i] > k else -1
count[d] += 1
res = count[0] + count[1] # 初始化结果，包括单个元素 k 的子数组
d = 0
# 从 k 的位置向右扫描，更新平衡值 d
for i in range(p + 1, n):
d += 1 if nums[i] < k else -1
res += count[d] + count[d+1] # 用之前的 count 数组值来计算符合条件的子数组数量
return res
在这个算法中，平衡值`d`用于跟踪数组中大于和小于中位数`k`的元素数量之间的差异。具体来说，当遍历数组时，每遇到一个大于`k`的元素，`d`增加1；每遇到一个小于`k`的元素，`d`减少1。这样，`d`的值可以看作是一个累积差值，表示当前子数组中大于`k`的元素与小于`k`的元素的数量差。当`d`为0或接近0的值时（如1），表示子数组中大于和小于`k`的元素数量大致相等，从而使得`k`可能是该子数组的中位数。通过统计这些平衡值的出现频次，我们可以计算出所有可能的以`k`为中位数的子数组数量。
初始化`count[0]`为1是基于考虑，当我们开始考察任何子数组时，最初没有任何元素包括在内，因此没有任何大于或小于`k`的元素，使得初始平衡值`d`为0。这相当于在统计中创建了一个基准点，即在任何元素被考虑之前，已经存在一个平衡值为0的状态。这是必要的，因为它允许算法正确地统计那些从`k`开始并且包含`k`的子数组。如果不将`count[0]`初始化为1，则这些情况将会被漏计。
向左扫描时，我们实际上是在计算以`k`为结束位置的子数组的平衡状态。在这种情况下，当我们遇到一个大于`k`的元素时，增加`d`是因为这增加了子数组中大于`k`的元素的计数，使得平衡向大于`k`的方向倾斜。相反，当遇到一个小于`k`的元素时，我们减少`d`，因为这会使平衡向小于`k`的方向倾斜，从而纠正平衡值以反映当前子数组中元素的实际分布。这种计数方式是为了确保`d`正确反映了从当前位置到`k`的每个元素对平衡状态的影响。