Hard

题目描述

给你一个整数数组 nums 和一个整数 target。

返回 nums 中以 target 为多数元素的子数组数量。

子数组的多数元素是指在该子数组中出现次数严格大于一半的元素。

示例 1：

输入：nums = [1,2,2,3], target = 2
输出：5
解释：
以 target = 2 为多数元素的有效子数组：
	nums[1..1] = [2]
	nums[2..2] = [2]
	nums[1..2] = [2,2]
	nums[0..2] = [1,2,2]
	nums[1..3] = [2,2,3]
因此有 5 个这样的子数组。

示例 2：

输入：nums = [1,1,1,1], target = 1
输出：10
解释：
所有 10 个子数组都以 1 为多数元素。

示例 3：

输入：nums = [1,2,3], target = 4
输出：0
解释：
target = 4 在 nums 中根本没有出现。因此，不可能有任何子数组以 4 为多数元素。答案是 0。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= target <= 10^9

解题思路

这道题要求计算以 target 为多数元素的子数组数量。关键思路是将问题转换为前缀和的比较问题。

核心思想：

  1. 将数组转换为 +1/-1 数组：如果 nums[i] == target 则为 +1，否则为 -1
  2. 计算前缀和数组 pref，其中 pref[i] 表示从开头到位置 i-1 的累计和
  3. 对于子数组 [i, j]，如果 target 是多数元素，则 pref[j+1] > pref[i]
  4. 问题转化为统计满足 pref[j] > pref[i] 且 i < j 的对数

算法步骤：

  1. 首先检查 target 是否在数组中存在，不存在则直接返回 0
  2. 构建转换后的数组和前缀和
  3. 使用树状数组或有序映射来高效统计逆序对的数量
  4. 对前缀和进行坐标压缩，然后遍历每个前缀和，查询之前有多少个更小的前缀和

这种方法的时间复杂度为 O(n log n)，空间复杂度为 O(n)，是处理此类问题的经典方法。

代码实现

class Solution {
public:
    long long countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        
        // Check if target exists
        bool found = false;
        for (int x : nums) {
            if (x == target) {
                found = true;
                break;
            }
        }
        if (!found) return 0;
        
        // Convert to +1/-1 array and build prefix sums
        vector<int> pref(n + 1, 0);
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + (nums[i] == target ? 1 : -1);
        }
        
        // Coordinate compression
        vector<int> vals = pref;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        
        // Count pairs (i < j) with pref[j] > pref[i]
        long long ans = 0;
        map<int, int> cnt;
        
        for (int i = 0; i <= n; i++) {
            // Count how many previous pref values are < current
            auto it = cnt.lower_bound(pref[i]);
            for (auto it2 = cnt.begin(); it2 != it; ++it2) {
                ans += it2->second;
            }
            cnt[pref[i]]++;
        }
        
        return ans;
    }
};

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        
        # Check if target exists
        if target not in nums:
            return 0
        
        # Convert to +1/-1 array and build prefix sums
        pref = [0] * (n + 1)
        for i in range(n):
            pref[i + 1] = pref[i] + (1 if nums[i] == target else -1)
        
        # Count pairs (i < j) with pref[j] > pref[i]
        ans = 0
        from collections import defaultdict
        cnt = defaultdict(int)
        
        for i in range(n + 1):
            # Count how many previous pref values are < current
            for val in cnt:
                if val < pref[i]:
                    ans += cnt[val]
            cnt[pref[i]] += 1
        
        return ans

public class Solution {
    public long CountMajoritySubarrays(int[] nums, int target) {
        int n = nums.Length;
        
        // Check if target exists
        bool found = false;
        foreach (int x in nums) {
            if (x == target) {
                found = true;
                break;
            }
        }
        if (!found) return 0;
        
        // Convert to +1/-1 array and build prefix sums
        int[] pref = new int[n + 1];
        for (int i = 0; i < n; i++) {
            pref[i + 1] = pref[i] + (nums[i] == target ? 1 : -1);
        }
        
        // Count pairs (i < j) with pref[j] > pref[i]
        long ans = 0;
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        
        for (int i = 0; i <= n; i++) {
            // Count how many previous pref values are < current
            foreach (var kvp in cnt) {
                if (kvp.Key < pref[i]) {
                    ans += kvp.Value;
                }
            }
            
            if (cnt.ContainsKey(pref[i])) {
                cnt[pref[i]]++;
            } else {
                cnt[pref[i]] = 1;
            }
        }
        
        return ans;
    }
}

var countMajoritySubarrays = function(nums, target) {
    const n = nums.length;
    
    // Check if target exists
    if (!nums.includes(target)) {
        return 0;
    }
    
    // Convert to +1/-1 array and build prefix sums
    const pref = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)当前实现需要遍历所有前缀和对，优化版本可达到 O(n log n)
空间复杂度O(n)需要存储前缀和数组和哈希表