2023-03-16 LeetCode：2488. 统计中位数为

2488. 统计中位数为 K 的子数组

问题描述

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

• 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
• 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
• 子数组是数组中的一个连续部分。

示例

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

解题思路

核心思路：前缀和

1. 先将数组nums进行处理，大于、小于、等于k的num，转换为1、-1、0；并记录下k所在的位置；
2. 遍历数组，在未找到k时，统计前缀和，并将前缀和丢入map中，统计数量；找到k后，可以开始计算结果了，结果就是当前前缀和与map中的前缀和相同或大于1的数量的累加。

代码示例（JAVA）

class Solution {
    public int countSubarrays(int[] nums, int k) {
        // 准备前缀和数据
        int length = nums.length, kIndex = -1;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            if (nums[i] > k) {
                arr[i] = 1;
            } else if (nums[i] < k) {
                arr[i] = -1;
            } else {
                arr[i] = 0;
                kIndex = i;
            }
        }
        // 前缀和+hashmap
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, sum = 0;
        for (int i = -1; i < length; i++) {
            sum += (i >= 0 ? arr[i] : 0);
            // 将到k之前的前缀和存入map
            if (i < kIndex) {
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            } else {
                // 到k之后，找符合的个数
                res += map.getOrDefault(sum, 0);
                res += map.getOrDefault(sum - 1, 0);
            }
        }
        return res;
    }
}

时间复杂度：O(n)