# 2488. Count Subarrays With Median K
###### tags: `Leetcode` `Hard` `HashMap`
Link: https://leetcode.com/problems/count-subarrays-with-median-k/description/
## 思路
思路参考[这里](https://leetcode.com/problems/count-subarrays-with-median-k/solutions/2851940/balance/)

A subarray has a median k if:
- It includes k
- Count n[i] < k is equal to count n[i] > k (odd-size subarrays).
- Count n[i] < k is one less than count n[i] > k (even-size subarrays).

Or, in other words, the balance between the count of smaller and larger elements is zero or one.

我们先找到所有以k为左端点的subarray的balance 并把count存进hashmap里面
然后我们遍历以k为右端点的subarray的balance 假设现在的balance是```bal``` 那么map[-bal]+map[-bal+1]就是以当前点为左端点的median为k的subarray的数目

## Code

class Solution {
    public int countSubarrays(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int p = 0, res = 0;
        for(int i=0; i<n; i++){
            if(nums[i]==k){
                p = i;
                break;
            }
        }
        int bal = 0;
        for(int i=p; i<n; i++){
            if(nums[i]==k) bal += 0;
            else bal += nums[i]<k?-1:1;
            map.put(bal, map.getOrDefault(bal, 0)+1);
        }
        bal = 0;
        for(int i=p; i>=0; i--){
            if(nums[i]==k) bal += 0;
            else bal += nums[i]<k?-1:1;
            res += map.getOrDefault(-bal, 0)+map.getOrDefault(-bal+1, 0);
        }
        return res;
    }
}