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;
    }
};

2026年6月26日更新，加上使用 BIT 解題的寫法

Python 程式碼

Runtime: 86 ms, beats 86.04%. Memory: 19.59 MB, beats 29.28%.

class BIT:
    # 自訂 binary indexed tree 類別
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def lowbit(self, x):
        return x & (-x)

    def update(self, i, delta):
        # 單點更新
        while i <= self.n:
            self.tree[i] += delta
            i += self.lowbit(i)

    def query(self, i):
        # 單點查詢，查詢 self.tree[0] ~ self.tree[i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self.lowbit(i)
        return total

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)  # 長度
        # 更新時依序加入 nums 的數值，記錄此時 target 的數量與其它數字數量的差值，數量差值的範圍是 [-n, n]，需要平移才能存入 BIT 之中
        offset = n + 1
        # 用自訂類別 BIT 建立物件
        bit = BIT(2*n + 1)  # 平移後的最大索引值為 2*n + 1
        # 答案、目前的 target 與其它數字數量差值，皆預設為 0
        ans, curr = 0, 0
        # 初始化 BIT，一開始 curr = 0，次數 1
        bit.update(curr + offset, 1)
        # 依序從 nums 取出數字 nums，更新 curr 及 bit
        for num in nums:
            # 更新 curr
            if num == target: curr += 1
            else: curr -= 1
            # 更新 ans，加上小於 curr 的數量，索引值平移為 curr - 1 + offset
            ans += bit.query(curr - 1 + offset)
            # 更新 bit，curr 對應的數量加 1，索引值平移為 curr + offset
            bit.update(curr + offset, 1)
        # 回傳答案
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 42.80 MB, beats 18.61%.

/* 自訂 binary indexed tree 類別 */
class BIT {
private:
    int n;
    vector<long long> tree;

    int lowbit(int x) {
        return x & (-x);
    }

public:
    BIT(int size) {
        n = size;
        tree.assign(n+1, 0);
    }

    void update(int i, long long delta) {
        while(i <= n) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }

    long long query(int i) {
        long long total = 0;
        while(i > 0) {
            total += tree[i];
            i -= lowbit(i);
        }
        return total;
    }
};

class Solution {
public:
    long long countMajoritySubarrays(vector<int>& nums, int target) {
        int n = (int)nums.size();  // 數量
        int offset = n + 1;  // 索引值平移量，因為 bit 之中儲存的數量差範圍為 [-n, n]，平移後為 [1, 2*n + 1]
        /* 初始化 BIT */
        BIT bit(2*n + 1);  // 資料長度 2*n + 1
        bit.update(offset, 1);  // 數量差 0，次數 1
        /* 依序從 nums 取出數字 nums，更新 curr 及 bit */
        long long ans = 0, curr = 0;
        for(int num : nums) {
            // 更新 curr
            if (num == target) curr++;
            else curr--;
            // 更新 ans，加上小於 curr 的數量，索引值平移為 curr - 1 + offset
            ans += bit.query(curr - 1 + offset);
            // 更新 bit，curr 對應的數量加 1，索引值平移為 curr + offset
            bit.update(curr + offset, 1);
        }
        return ans;
    }
};