Hard

题目描述

给你一个大小为 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 中的整数互不相同。

解题思路

解题思路

这道题的关键洞察是将数组进行转换，让问题变得更容易处理：

核心思想

  1. 数组转换：将原数组按照与 k 的关系转换：

    • 大于 k 的数变为 1
    • 小于 k 的数变为 -1
    • 等于 k 的数变为 0

  2. 中位数性质：转换后，如果一个子数组的中位数是 k（即原来的 0），那么这个子数组必须满足：

    • 包含 k（即转换后的 0）
    • 前缀和为 0 或 1（取决于子数组长度的奇偶性）

算法步骤

  1. 找到 k 在数组中的位置
  2. 从 k 的位置开始，分别向左右扩展，计算前缀和
  3. 使用哈希表记录左侧各个前缀和出现的次数
  4. 对于右侧的每个前缀和，查找左侧能够配对的前缀和数量

配对规则

  • 如果子数组长度为奇数，需要左右前缀和相等
  • 如果子数组长度为偶数，需要右侧前缀和比左侧多 1

这样可以保证包含 k 的子数组的前缀和为 0 或 1，从而确保 k 是中位数。

代码实现

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int pos = 0;
        
        // 找到k的位置
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                pos = i;
                break;
            }
        }
        
        // 转换数组：>k为1，<k为-1，=k为0
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            if (nums[i] > k) arr[i] = 1;
            else if (nums[i] < k) arr[i] = -1;
            else arr[i] = 0;
        }
        
        unordered_map<int, int> leftCount;
        leftCount[0] = 1; // 空前缀
        
        // 计算左侧前缀和
        int sum = 0;
        for (int i = pos - 1; i >= 0; i--) {
            sum += arr[i];
            leftCount[sum]++;
        }
        
        int result = leftCount[0]; // 只包含k的情况
        
        // 计算右侧前缀和并统计答案
        sum = 0;
        for (int i = pos + 1; i < n; i++) {
            sum += arr[i];
            // 奇数长度：左右前缀和相等
            result += leftCount[sum];
            // 偶数长度：右侧比左侧多1
            result += leftCount[sum - 1];
        }
        
        return result;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pos = nums.index(k)
        
        # 转换数组：>k为1，<k为-1，=k为0
        arr = []
        for num in nums:
            if num > k:
                arr.append(1)
            elif num < k:
                arr.append(-1)
            else:
                arr.append(0)
        
        from collections import defaultdict
        left_count = defaultdict(int)
        left_count[0] = 1  # 空前缀
        
        # 计算左侧前缀和
        prefix_sum = 0
        for i in range(pos - 1, -1, -1):
            prefix_sum += arr[i]
            left_count[prefix_sum] += 1
        
        result = left_count[0]  # 只包含k的情况
        
        # 计算右侧前缀和并统计答案
        prefix_sum = 0
        for i in range(pos + 1, n):
            prefix_sum += arr[i]
            # 奇数长度：左右前缀和相等
            result += left_count[prefix_sum]
            # 偶数长度：右侧比左侧多1
            result += left_count[prefix_sum - 1]
        
        return result

public class Solution {
    public int CountSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int pos = Array.IndexOf(nums, k);
        
        // 转换数组：>k为1，<k为-1，=k为0
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            if (nums[i] > k) arr[i] = 1;
            else if (nums[i] < k) arr[i] = -1;
            else arr[i] = 0;
        }
        
        Dictionary<int, int> leftCount = new Dictionary<int, int>();
        leftCount[0] = 1; // 空前缀
        
        // 计算左侧前缀和
        int sum = 0;
        for (int i = pos - 1; i >= 0; i--) {
            sum += arr[i];
            leftCount[sum] = leftCount.GetValueOrDefault(sum, 0) + 1;
        }
        
        int result = leftCount.GetValueOrDefault(0, 0); // 只包含k的情况
        
        // 计算右侧前缀和并统计答案
        sum = 0;
        for (int i = pos + 1; i < n; i++) {
            sum += arr[i];
            // 奇数长度：左右前缀和相等
            result += leftCount.GetValueOrDefault(sum, 0);
            // 偶数长度：右侧比左侧多1
            result += leftCount.GetValueOrDefault(sum - 1, 0);
        }
        
        return result;
    }
}

var countSubarrays = function(nums, k) {
    const n = nums.length;
    const pos = nums.indexOf(k);
    
    // 转换数组：>k为1，<k为-1，=k为0
    const arr = nums.map(num => {
        if (num > k) return 1;
        if (num < k) return -1;
        return 0;
    });
    
    const leftCount = new Map();
    leftCount.set(0, 1); // 空前缀
    
    // 计算左侧前缀和
    let sum = 0;
    for (let i = pos - 1; i >= 0; i--) {
        sum += arr[i];
        leftCount.set(sum, (leftCount.get(sum) || 0) + 1);
    }
    
    let result = leftCount.get(0) || 0; // 只包含k的情况
    
    // 计算右侧前缀和并统计答案
    sum = 0;
    for (let i = pos + 1; i < n; i++) {
        sum += arr[i];
        // 奇数长度：左右前缀和相等
        result += leftCount.get(sum) || 0;
        // 偶数长度：右侧比左侧多1
        result += leftCount.get(sum - 1) || 0;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次O(n)
空间复杂度O(n)哈希表最多存储n个不同的前缀和

相关题目