1.题目

给你一个长度为 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.length

1 <= n <= 10

⁵


1 <= nums[i], k <= n

nums 中的整数互不相同

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/count-subarrays-with-median-k

2.思路

（1）前缀和 & 哈希表


思路参考

本题官方题解

。

3.代码实现（Java）

//思路1————前缀和 & 哈希表
class Solution {
    public int countSubarrays(int[] nums, int k) {
        int length = nums.length;
        //kIndex 表示正整数 k 在数组 nums 中的下标
        int kIndex = -1;
        for (int i = 0; i < length; i++) {
            if (nums[i] == k) {
                kIndex = i;
                break;
            }
        }
        int res = 0;
        //记录转换后的数组的每个前缀和以及对应出现的次数
        Map<Integer, Integer> counts = new HashMap<>();
        counts.put(0, 1);
        int sum = 0;
        for (int i = 0; i < length; i++) {
            // sum 表示转换后的数组 nums[0...i] 之和
            sum += Integer.compare(nums[i], k);
            if (i < kIndex) {
                //下标 i + 1 可以作为中位数等于 k 的非空子数组的开始下标，将 sum 在哈希表中的出现次数加 1
                counts.put(sum, counts.getOrDefault(sum, 0) + 1);
            } else {
                /*
                    下标 i 可以作为中位数等于 k 的非空子数组的结束下标，从哈希表中获得前缀和 sum 的出现
                    次数 prev0 与前缀和 sum − 1 的出现次数 prev1，则以下标 i 作为结束下标且中位数等于 
                    k 的非空子数组的数目是 prev0 + prev1，将答案增加 prev0 + prev1
                */
                int prev0 = counts.getOrDefault(sum, 0);
                int prev1 = counts.getOrDefault(sum - 1, 0);
                res += prev0 + prev1;
            }
        }
        return res;
    }
}