Medium

题目描述

给你一个整数数组 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 <= 1000
  • 1 <= nums[i] <= 10^9
  • 1 <= target <= 10^9

解题思路

解题思路

这道题要求统计以 target 为主要元素的子数组数量。主要元素的定义是在子数组中出现次数严格超过一半。

暴力枚举法（推荐）

由于数组长度限制为 1000，我们可以使用暴力枚举的方法：

  1. 枚举所有可能的子数组，对于每个起始位置 i，枚举所有可能的结束位置 j
  2. 对于每个子数组 nums[i:j+1]，统计 target 出现的次数
  3. 如果 target 出现次数严格大于子数组长度的一半，则计数器加一

判断条件：count(target) > length / 2 等价于 2 * count(target) > length

优化思路

可以在枚举过程中增量计算 target 的出现次数，避免每次重新计算整个子数组。当我们固定左端点 i 并逐步扩展右端点 j 时，只需要检查新加入的元素是否等于 target。

时间复杂度分析

由于需要枚举所有子数组，时间复杂度为 O(n²)，其中 n 是数组长度。对于本题的数据范围（n ≤ 1000），这种复杂度是可以接受的。

代码实现

class Solution {
public:
    int countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == target) {
                    count++;
                }
                int length = j - i + 1;
                if (2 * count > length) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        result = 0
        
        for i in range(n):
            count = 0
            for j in range(i, n):
                if nums[j] == target:
                    count += 1
                length = j - i + 1
                if 2 * count > length:
                    result += 1
        
        return result

public class Solution {
    public int CountMajoritySubarrays(int[] nums, int target) {
        int n = nums.Length;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == target) {
                    count++;
                }
                int length = j - i + 1;
                if (2 * count > length) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

var countMajoritySubarrays = function(nums, target) {
    let count = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let targetCount = 0;
        for (let j = i; j < n; j++) {
            if (nums[j] === target) {
                targetCount++;
            }
            const subarrayLength = j - i + 1;
            if (targetCount > subarrayLength / 2) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n²)
空间复杂度O(1)

其中 n 为数组 nums 的长度。需要枚举所有可能的子数组，总共有 O(n²) 个子数组，每个子数组的处理时间为 O(1)，因此总时间复杂度为 O(n²)。算法只使用了常数级别的额外空间。