LeetCode 解題筆記：3739. Count Subarrays With Majority Element II

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


LeetCode 題目連結：3739. Count Subarrays With Majority Element II

解題想法

困難題，3737. Count Subarrays With Majority Element I 的加強版，$nums$ 的長度從 $1000$ 增加到 $10^5$，如果用時間複雜度為 $O(n^2)$ 會超時，要改用二元索引樹 (binary indexed tree, BIT)。bit 之中儲存的資料為 $target$ 的數量與其它數字的數量差值 $curr$ 出現的次數，但由於 $curr$ 的範圍是 $-n$ ~ $n$，bit 的資料是 1-indexed，$curr$ 需要加上位移量 $offset = n+1$ 平移至 $1$ ~ $2n + 1$ 才能存入 bit 之中。建立 bit 物件之後，初始化為 bit.(0, 1)，數量差 0、次數 1。接下來依序讀取 $nums$ 的資料 $num$，更新 $curr$，利用 bit.query(curr - 1 + offset) 更新答案 ans，再用 bit.update(curr + offset, 1) 更新 bit。最後回傳 ans。可以將這題的程式碼拿來解 3737. Count Subarrays With Majority Element I，速度快很多。

Python 程式碼

Runtime: 1035 ms, beats 26.13%. Memory: 32.39 MB, beats 90.99%.

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: 19 ms, beats 78.15%. Memory: 101.28 MB, beats 64.90%.

/* 自訂 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;
    }
};