LeetCode 解題筆記：3737. Count Subarrays With Majority Element I

作者：王一哲
日期：2026年6月25日


LeetCode 題目連結：3737. Count Subarrays With Majority Element I

解題想法

中等難度題。我的寫法時間複雜度為 $O(n^2)$，大約分成以下個步驟：

1. 先用一層 for 迴圈更新右端點 $right$ 從 $0$ 到 $nums$ 的長度 $n$，依照 $nums[right]$ 更新 $nums[0]$ 到 $nums[right]$ 的 $target$ 數量 $cnt$。
2. 複製 $cnt$ 的值到 $newCnt$
3. 再用一層 for 迴圈更新左端點 $left$ 從 $0$ 到 $right$，先檢查 $cnt$ 是否大於 $(right - left + 1) / 2$，如果條件成立，答案 $ans$ 加1；再檢查 $nums[left]$ 是否等於 $target$，如果條件成立 $newCnt$ 減 1。

Python 程式碼

Runtime: 1763 ms, beats 52.00%. Memory: 19.34 MB, beats 90.22%.

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n, cnt, ans = len(nums), 0, 0  # 長度，target 的數量，答案
        for right in range(n):  # 右端點
            if nums[right] == target: cnt += 1  # 更新 cnt
            newCnt = cnt  # 複製 cnt
            for left in range(right + 1):  # 左端點 0 ~ left
                if newCnt > (right - left + 1) // 2: ans += 1  # 檢查 newCnt 是否大於長度的 1/2
                if nums[left] == target: newCnt -= 1  # 更新 newCnt
        return ans

C++ 程式碼

Runtime: 31 ms, beats 82.13%. Memory: 39.60 MB, beats 75.60%.

class Solution {
public:
    int countMajoritySubarrays(vector<int>& nums, int target) {
        int n = (int)nums.size(), cnt = 0, ans = 0;  // 長度，target 的數量，答案
        for(int right = 0; right < n; right++) {  // 右端點
            if (nums[right] == target) cnt++;  // 更新 cnt
            int newCnt = cnt;  // 複製 cnt
            for(int left = 0; left <= right; left++) {  // 左端點 0 ~ left
                if (newCnt > (right - left + 1) / 2) ans++;  // 檢查 newCnt 是否大於長度的 1/2
                if (nums[left] == target) newCnt--;  // 更新 newCnt
            }
        }
        return ans;
    }
};