题目：

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。

注意：

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

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i], k <= n
nums 中的整数互不相同

解题思路：

先找到K的下标

从K下标开始往左遍历一次，往右遍历一次。

将题目转化一下：奇数 => 小于 = 大于

​ 偶数 => 小于 + 1 = 大于

1
2
3
4
5
6
7
8
9
奇数：

左侧小于 + 右侧小于 = 左侧大于 + 右侧大于
左侧小于 - 右侧大于 = 左侧小于 - 右侧大于

偶数：

左侧小于 + 右侧小于 + 1 = 左侧大于 + 右侧大于
左侧小于 - 右侧大于 + 1 = 左侧小于 - 右侧大于

代码：

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        # 查找K的下标
        pos = nums.index(k)
        cnt = Counter()
        cnt[0] = 1
        c = 0
        for i in range(pos + 1, len(nums)):
            c += 1 if nums[i] > k else -1
            cnt[c] += 1
        
        c = 0
        ans = cnt[0] + cnt[1]
        for i in range(pos - 1, -1, -1):
            c += 1 if nums[i] < k else -1
            ans += cnt[c] + cnt[c + 1]
        
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int countSubarrays(vector<int> &nums, int k) {
        int pos, n = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == k)
            {
                pos = i;
                break;
            }
        }
        unordered_map<int, int> cnt;
        cnt[0] = 1; // i=pos 的时候 c 是 0，直接记到 cnt 中，这样下面不是大于就是小于
        for (int i = pos + 1, c = 0; i < n; ++i) {
            c += nums[i] > k ? 1 : -1;
            ++cnt[c];
        }

        int ans = cnt[0] + cnt[1]; // i=pos 的时候 c 是 0，直接加到答案中，这样下面不是大于就是小于
        for (int i = pos - 1, c = 0; i >= 0; --i) {
            c += nums[i] < k ? 1 : -1;
            ans += cnt[c] + cnt[c + 1];
        }
        return ans;
    }
};