2026-03-26：统计主要元素子数组数目Ⅰ。用go语言，给定一个整数数组 nums 和一个整数 target。 你要统计数组中连续且非空的所有子数组中

2026-03-26：统计主要元素子数组数目Ⅰ。用go语言，给定一个整数数组 nums 和一个整数 target。

你要统计数组中连续且非空的所有子数组中，满足如下条件的子数组数量：在该子数组里，target 这个数出现的次数严格大于子数组长度的一半。

也就是说，若子数组长度为 len，target 在其中出现了 cnt 次，则必须满足 cnt > len/2。

返回满足条件的子数组总数。

1 <= nums.length <= 1000。

1 <= nums[i] <= 1000000000。

1 <= target <= 1000000000。

输入: 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 个这样的子数组。

题目来自力扣3737。

算法详细执行过程拆解

我们以输入 nums = [1,2,2,3]，target = 2 为例，分步骤、逐元素讲解代码的执行逻辑，全程不写代码，只讲核心思路和计算过程。

一、核心前置理解

题目要求：统计所有连续非空子数组中，target 出现次数 严格大于 子数组长度一半的子数组数量。

• • 子数组长度为 L，target 出现次数为 c，满足 c > L/2 即符合条件。
• • 等价条件：target 出现次数 - 非target 元素次数 > 0（推导：c > (L-c) → 2c-L >0 → c-(L-c) >0）。

代码的核心思路：用前缀和 + 计数数组，快速统计满足条件的子数组数量，避免暴力枚举所有子数组。

二、初始化阶段（遍历数组前）

1. 1. 数组长度 n = 4（nums 有4个元素）。
2. 2. 创建计数数组 cnt：长度为 4*2+1=9，用来记录前缀和数值出现的次数，初始全为0。
3. 3. 初始赋值：cnt[4] = 1（前缀和的初始基准值，对应前缀和为0）。
4. 4. 定义两个关键变量：
   • • s：当前前缀和的偏移值，初始为 4（对应前缀和0）；
   • • f：记录以当前元素结尾的符合条件的子数组数量，初始为0；
5. 5. 结果变量 ans：最终总数量，初始为0。

三、逐元素遍历数组（核心执行过程）

我们按顺序遍历 1 → 2 → 2 → 3 四个元素，每一步都做判断、更新变量、统计数量、更新计数数组四个操作。

第一步：遍历第一个元素 x = 1（不是 target=2）

1. 1. 判断元素：x 不等于 target，执行非目标值逻辑：
   • • 前缀和偏移值 s 减1 → s = 4-1 = 3；
   • • 用当前 s 对应的计数数组值，减少 f → f = 0 - cnt[3] = 0-0 = 0；
2. 2. 累加结果：ans 加上当前 f → ans = 0；
3. 3. 更新计数数组：cnt[3] 加1 → cnt[3] = 1；
4. 4. 当前状态：s=3，f=0，ans=0，cnt[3]=1。

第二步：遍历第二个元素 x = 2（是 target=2）

1. 1. 判断元素：x 等于 target，执行目标值逻辑：
   • • 用当前 s 对应的计数数组值，增加 f → f = 0 + cnt[3] = 0+1 = 1；
   • • 前缀和偏移值 s 加1 → s = 3+1 = 4；
2. 2. 累加结果：ans 加上当前 f → ans = 0+1 = 1；
3. 3. 更新计数数组：cnt[4] 加1 → cnt[4] = 1+1 = 2；
4. 4. 当前状态：s=4，f=1，ans=1，cnt[4]=2。 ✅ 此时新增1个符合条件的子数组：[2]（下标1）。

第三步：遍历第三个元素 x = 2（是 target=2）

1. 1. 判断元素：x 等于 target，执行目标值逻辑：
   • • 用当前 s 对应的计数数组值，增加 f → f = 1 + cnt[4] = 1+2 = 3；
   • • 前缀和偏移值 s 加1 → s = 4+1 = 5；
2. 2. 累加结果：ans 加上当前 f → ans = 1+3 = 4；
3. 3. 更新计数数组：cnt[5] 加1 → cnt[5] = 1；
4. 4. 当前状态：s=5，f=3，ans=4，cnt[5]=1。 ✅ 此时新增3个符合条件的子数组：[2]（下标2）、[2,2]（下标1-2）、[1,2,2]（下标0-2）。

第四步：遍历第四个元素 x = 3（不是 target=2）

1. 1. 判断元素：x 不等于 target，执行非目标值逻辑：
   • • 前缀和偏移值 s 减1 → s = 5-1 = 4；
   • • 用当前 s 对应的计数数组值，减少 f → f = 3 - cnt[4] = 3-2 = 1；
2. 2. 累加结果：ans 加上当前 f → ans = 4+1 = 5；
3. 3. 更新计数数组：cnt[4] 加1 → cnt[4] = 2+1 = 3；
4. 4. 当前状态：s=4，f=1，ans=5，cnt[4]=3。 ✅ 此时新增1个符合条件的子数组：[2,2,3]（下标1-3）。

四、最终结果

遍历结束后，ans = 5，与题目输出完全一致。

时间复杂度 & 额外空间复杂度

1. 时间复杂度

• • 代码只对数组进行了一次从头到尾的遍历，每个元素仅执行常数次操作（判断、加减变量、数组赋值）；
• • 数组长度为 n，因此总时间复杂度为 O(n)。

2. 额外空间复杂度

• • 代码中创建了一个计数数组 cnt，长度为 2n+1，是唯一的额外空间；
• • 其他变量（s、f、ans、n）均为常数级空间，不随输入规模变化；
• • 因此总额外空间复杂度为 O(n)。

总结

1. 1. 执行过程：通过前缀和偏移标记 target 与非 target 的数量差，用计数数组记录前缀和出现次数，逐元素统计以当前元素结尾的符合条件子数组数量，最终累加得到总数；
2. 2. 时间复杂度：O(n)（线性遍历）；
3. 3. 额外空间复杂度：O(n)（计数数组）。

Go完整代码如下：

package main

import (
    "fmt"
)

func countMajoritySubarrays(nums []int, target int) (ans int64) {
    n := len(nums)
    cnt := make([]int, n*2+1)
    cnt[n] = 1
    s, f := n, 0
    for _, x := range nums {
        if x == target {
            f += cnt[s]
            s++
        } else {
            s--
            f -= cnt[s]
        }
        ans += int64(f)
        cnt[s]++
    }
    return
}

func main() {
    nums := []int{1, 2, 2, 3}
    target := 2
    result := countMajoritySubarrays(nums, target)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-

defcountMajoritySubarrays(nums, target):
    n = len(nums)
    # 偏移量 n，避免负数下标
    offset = n
    cnt = [0] * (n * 2 + 1)
    cnt[offset] = 1
    
    s = offset
    f = 0
    ans = 0
    
    for x in nums:
        if x == target:
            f += cnt[s]
            s += 1
        else:
            s -= 1
            f -= cnt[s]
        
        ans += f
        cnt[s] += 1
    
    return ans

defmain():
    nums = [1, 2, 2, 3]
    target = 2
    result = countMajoritySubarrays(nums, target)
    print(result)

if __name__ == "__main__":
    main()

在这里插入图片描述

C++完整代码如下：

#include <iostream>
#include <vector>
usingnamespace std;

long long countMajoritySubarrays(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> cnt(n * 2 + 1, 0);
    cnt[n] = 1;
    int s = n, f = 0;
    longlong ans = 0;

    for (int x : nums) {
        if (x == target) {
            f += cnt[s];
            s++;
        } else {
            s--;
            f -= cnt[s];
        }
        ans += f;
        cnt[s]++;
    }
    return ans;
}

int main() {
    vector<int> nums = {1, 2, 2, 3};
    int target = 2;
    longlong result = countMajoritySubarrays(nums, target);
    cout << result << endl;
    return0;
}

在这里插入图片描述

·

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。

·