力扣---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 <= 105
    1 <= nums[i], k <= n
    nums 中的整数互不相同
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-subarrays-with-median-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

摸打爬滚，在idea里面各种debug，终于是做出来了。

由于中位数的特点，只需要判断一个数是大于k还是小于k即可，很容易就可以联想到前缀和来做。

以k为中位数的数组，从k的位置来看，有三种：

1. k在该数组的最左边。

2. k在该数组的最右边。

3. k在该数组的中间。

而判断该数组是否以k为中位数，可以将大于k的数设为1，小于k的数设为-1，等于k的数设为0，数组中的元素和相加等于0或1时，该数组即是符合题目要求的以k为中位数的数组。

class Solution {
    public int countSubarrays(int[] nums, int k) {
//        寻找对应的下标
        int index = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] == k) {
                index = i;
                break;
            }
        }
//        它自身也算一个。
        int res = 1;
        Map<Integer, Integer> map = new HashMap<>();
//        前缀和，计算某个位置到k所在位置的值，大于k的+1，小于k的-1.等于k的=0
        nums[index] = 0;
//        从k所在位置向左遍历，将k作为数组的最右点，值为1或0的即是中位数为k的数组。
        for (int i = index - 1; i >= 0; i --) {
            nums[i] = nums[i + 1] + (nums[i] > k ? 1 : -1);
            if (nums[i] == 0 || nums[i] == 1) {
                res ++;
            }
//            记录到k指定前缀和的数量
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
//        从k向右遍历。
        for (int i = index + 1; i < nums.length; i ++) {
            nums[i] = nums[i - 1] + (nums[i] > k ? 1 : -1);
//            以k为数组左边界的情况，和以k为右边界的相同。
            if (nums[i] == 0 || nums[i] == 1) {
                res ++;
            }
//            k在答案数组中间的情况，两边的前缀和差值为0或1时，即是以k为中位数的数组。
            if (map.containsKey(-nums[i])) {
                res += map.get(-nums[i]);
            }
            if (map.containsKey(1 - nums[i])) {
                res += map.get(1- nums[i]);
            }
        }
        return res;
    }
}