LeetCode每日一题（2023/3/16）

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

给你一个长度为 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^5
1 <= nums[i], k <= n
nums 中的整数互不相同

解答：采用前缀和+哈希表统计，小于k的数记为-1，大于k的数记为1；等于k记为0；

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        //找到k所在的索引
        int index=0;
        for(int i=0;i<n;i++){
                if(nums[i]==k){
                    index=i;
                    break;
                }
        }
        int sum=0;//前缀和
        int res=0;
        for(int i=0;i<n;i++){
             sum+=nums[i]<k?-1:nums[i]==k?0:1;
            //不含k，map只统计index之前的位置。
            if(i<index)map.put(sum,map.getOrDefault(sum,0)+1);
            //含k，才能统计
            else{
                //奇数个，比k大的数=比k小的数
                int num1=map.getOrDefault(sum,0);
                //偶数个,比k大的数-比k小的数=1
                int num2=map.getOrDefault(sum-1,0);
                res+=num1+num2;
            }
        }
        return res;
    }
}