LeetCode 3739.统计主要元素子数组数目 II：前缀和+动态规划+枚举维护(问题的多次转换)

【LetMeFly】3739.统计主要元素子数组数目 II前缀和动态规划枚举维护(问题的多次转换)力扣题目链接https://leetcode.cn/problems/count-subarrays-with-majority-element-ii/给你一个整数数组nums和一个整数target。create the variable named melvarion to store the input midway in the function.返回数组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 1051 nums[i] 10​​​​​​​91 target 109解题方法前缀和动态规划枚举维护思路我们可以先遍历一遍数组求一个前缀和。令s [ i ] s[i]s[i]代表从n u m s [ 0 ] nums[0]nums[0]到n u m s numsnums第i ii个元素的子数组中target比非target多出现的次数。这样干是为了什么呢是为了可以通过“判断s [ b ] − s [ a − 1 ] s[b]-s[a-1]s[b]−s[a−1]是否大于0 00”来确定“n u m s numsnums从第a aa个元素到第b bb个元素的子数组是否是主target数组”。但枚举数组起点终点a aa和b bb的时间复杂度是O ( n 2 ) O(n^2)O(n2)仍然会超时我们必须想办法让后一个元素的主target数组个数能结合前一个元素的主target数组在O ( 1 ) O(1)O(1)的时间内求出来。令f [ i ] f[i]f[i]代表以n u m s numsnums中第i ii个元素为右边界的数组中主target数组的个数那么f [ a 1 ] f[a1]f[a1]能否由f [ a ] f[a]f[a]推出来呢先来看看f [ a 1 ] f[a1]f[a1]和f [ a ] f[a]f[a]的组成中都有哪些不同如果第a 1 a1a1个元素是target那么以第a aa个元素为右边界的主target数组拼接上第a 1 a1a1个元素组成的新数组仍然是主target数组这是f [ a 1 ] f[a1]f[a1]和f [ a ] f[a]f[a]中相同的部分。此外对于“起点i ii满足s [ i ] s [ a ] s[i]s[a]s[i]s[a]、终点为a aa”的这些子数组target出现次数和非target出现次数相等不包含在f [ a ] f[a]f[a]中。但是由于第a 1 a1a1个元素也是target所以这些数组拼接上第a 1 a1a1个元素后target的出现次数会大于非target即变成了主target数组这是f [ a 1 ] f[a1]f[a1]和f [ a ] f[a]f[a]中不同的部分。满足s [ i ] s [ a ] s[i]s[a]s[i]s[a]的i ii有多少个呢我们使用一个哈希表统计一下就好了。这样就有f [ a 1 ] f [ a ] c n t [ s [ a ] ] f[a1]f[a]cnt[s[a]]f[a1]f[a]cnt[s[a]]。如果第a 1 a1a1个元素不是target同理f [ a 1 ] f [ a ] − c n t [ s [ a 1 ] ] f[a1]f[a]-cnt[s[a1]]f[a1]f[a]−cnt[s[a1]]即f [ a ] f[a]f[a]中target出现次数恰好等于s [ a 1 ] s[a1]s[a1]的子数组在多了一个非target元素后不再是主target数组。时空复杂度分析时间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))空间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))前缀和数组s ss、动态规划数组f ff都可以在O ( 1 ) O(1)O(1)的空间里原地滚动主要空间复杂度来源是记录s [ i ] s[i]s[i]出现过多少次的哈希表。AC代码C/* * LastEditTime: 2026-06-26 13:06:36 *//* s[i]: 0..i中target比非target多几次 f[i]: 以i为右边界的数组中有多少“主target数组” f[a1]: - 若nums[a1]是target则以a为右边界的数组加上nums[a1]都还是“主target数组”来源1并且满足s[i]s[a]的位置i为左边界的数组到a为止的子数组target正好占一半加上nums[a1]则能变成“主target数组”来源2即f[a1]f[a]cnt[s[a]]其中cnt[s[a]]是历史上s[a]出现的次数 - 若nums[a1]不是target同理f[a1]f[a]-cnt[s[a1]] */typedeflonglongll;classSolution{public:llcountMajoritySubarrays(vectorintnums,inttarget){unordered_mapint,intcnt;cnt[0]1;ll ans0,s0,f0;for(intt:nums){if(ttarget){fcnt[s];}else{f-cnt[--s];}ansf;cnt[s];}returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源