🔗 🟡 3737. Count Subarrays With Majority Element I

Problem Statement

題目簡述

給定整數陣列 nums 和整數 target，請計算有多少個非空子陣列滿足：target 在該子陣列中出現的次數嚴格大於子陣列長度的一半，也就是 target 是這個子陣列的多數元素。

Constraints

約束條件

$1 \leq \texttt{nums.length} \leq 1000$
$1 \leq \texttt{nums[i]} \leq 10^9$
$1 \leq \texttt{target} \leq 10^9$

思路：前綴和枚舉子陣列

本題的筆記中僅展示

O\left(n^2\right)

的解法，其餘複雜度更優的寫法請見 LeetCode 🔴 3739. Count Subarrays With Majority Element II 此篇筆記。

如果直接枚舉子陣列的所有左右端點 $[l, r]$ ，再逐段統計 target 出現次數，會多出一層掃描，整體為 $O(n^3)$ ，以本題的數據範圍來說是不接受的，因此需要可以考慮能不能把「某段裡 target 是否為多數元素」變成 $O(1)$ 判定。

等價轉換

對一個子陣列，設 target 的出現次數為 $cnt_{target}$ ，其餘元素的出現次數為 $cnt_{other}$ 。題目要求 target 出現次數嚴格超過子陣列長度的一半，也就是：

cnt_{target} > cnt_{other}

移項後，條件等價於：

cnt_{target} - cnt_{other} > 0

因此可以把子陣列中的每個元素做如下轉換：

等於 target 的位置記為 $+1$
不等於 target 的位置記為 $-1$

那麼一段子陣列的轉換後總和，正好就是：

cnt_{target} - cnt_{other}

所以問題變成：計算有多少個子陣列的轉換後區間和大於 $0$ 。

Tip

遇到「某元素出現次數是否超過一半」時，可以嘗試把目標元素變成 $+1$ ，其他元素變成 $-1$ 。這樣「多數」條件就會變成「區間和是否為正」。

用前綴和做到快速判定

有了上述轉換後，只要建立轉換陣列的前綴和，就能在 $O(1)$ 時間求出任意子陣列的總和。

不妨設轉換後的陣列為 $B$ ，其中：

B_i = \begin{cases} 1, & \text{if } nums[i] = target \\ -1, & \text{if } nums[i] \neq target \end{cases}

定義前綴和：

s_i = \sum_{k=0}^{i-1} B_k, \quad s_0 = 0

對於子陣列 $[l,r]$ ，如果前綴和差值滿足：

s_{r+1} - s_l > 0

就表示這段子陣列的 $cnt_{target} - cnt_{other} > 0$ ，也就是 target 是多數元素。

條件必須是嚴格大於

0

，不是大於等於

0

。如果區間和等於

0

，只代表 target 和非 target 的數量一樣多，並沒有嚴格超過一半。

因此只要枚舉所有子陣列，用前綴和差值判斷是否滿足題意即可。這樣就能把原本 $O(n^3)$ 的解法，降到 $O(n^2)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n^2)$ ，需要枚舉所有子陣列。
空間複雜度： $\mathcal{O}(n)$ ，需要儲存轉換後的前綴和。

Code

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        s = list(accumulate((1 if (x == target) else -1 for x in nums), initial=0))
        ans = 0
        for i in range(n):
            for j in range(i + 1):
                if s[i + 1] - s[j] > 0:
                    ans += 1
        return ans