统计中位数为 K 的子数组【LC2488】
给你一个长度为
n的数组nums，该数组由从1到n的 不同 整数组成。另给你一个正整数k。统计并返回
nums中的 中位数 等于k的非空子数组的数目。注意：
数组的中位数是按递增顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
- 例如，
[2,3,1,4]的中位数是2，[8,4,3,5,1]的中位数是4。
- 子数组是数组中的一个连续部分。
自己做的时候也是转换成了+1-1 ，但是是大于等于的+1，小于的-1，然后如果是中位数那么差为1，但是一部分案例不对，不愿细想了，时间就是个无底洞。
- 思路：
将子数组根据长度分为两种情况
- 长度为奇数时，「k是长为奇数的子数组的中位数」等价于「子数组中小于k的数的个数 === 大于k的数的个数」
- 这相当于「左侧小于 +右侧小于 = 左侧大于 + 右侧大于」。
变形得到「左侧小于 − 左侧大于 = 右侧大于 −右侧小于」。
- 长度为偶数时，「k是长为奇数的子数组的中位数」等价于「子数组中小于k的数的个数 === 大于k的数的个数」
- 这相当于「左侧小于 +右侧小于 = 左侧大于 + 右侧大于 - 1」。
变形得到「左侧小于 − 左侧大于 = 右侧大于 −右侧小于 -1」。
为了方便计算，把这四类数字等价转换，然后记录在数组cnt中：
- 左侧小于：在 k左侧且比 k 小的视作 1；
- 左侧大于：在 k 左侧且比 k 大的视作 −1；
- 右侧大于：在 k 右侧且比 k 大的视作 1；
右侧小于：在 k 右侧且比 k 小的视作 −1。
那么可以将目标值左侧的小于-左侧大于的值，放入数组cnt中，然后枚举右侧的端点r rr（包括自身），
以r 为右端点的奇数数组的数目为cnt[x]，偶数数组的数目为cnt[x-1]
实现
class Solution { public int countSubarrays(int[] nums, int k) { int n = nums.length; int i = 0; for (; nums[i] != k; ++i) {} int[] cnt = new int[n << 1 | 1]; int ans = 1; int x = 0; for (int j = i + 1; j < n; ++j) { x += nums[j] > k ? 1 : -1; if (x >= 0 && x <= 1) { ++ans; } ++cnt[x + n]; } x = 0; for (int j = i - 1; j >= 0; --j) { x += nums[j] > k ? 1 : -1; if (x >= 0 && x <= 1) { ++ans; } ans += cnt[-x + n] + cnt[-x + 1 + n]; } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/count-subarrays-with-median-k/solutions/2171706/python3javacgotypescript-yi-ti-yi-jie-bi-whsm/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
