📘 題目敘述
給你一個整數陣列 nums。
如果一個子陣列中，所有元素的 bitwise OR 結果，剛好等於這個子陣列中至少一個元素，則這個子陣列稱為 good。
請回傳 good subarray 的數量。
子陣列指的是陣列中一段連續且非空的區間。
這裡兩個整數 a 和 b 的 bitwise OR 記作
a | b。
條件限制
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
🧠 解題思路（最後TLE）
我這份寫法是直接枚舉每一個子陣列。
對每個起點 i，我一路往右延伸終點
j，同時維護：
- 目前這段子陣列的 OR 值
now - 這段子陣列裡出現過哪些數字
只要某一段 [i..j] 的 OR 值
now，剛好有出現在這段子陣列裡，那這段就是 good
subarray，答案加一。
這個想法本身是直接照題意檢查，所以很好理解。
但它的問題也很明顯：
- 我把所有子陣列都枚舉出來了
- 每一段還要維護一個
set
所以在
n 很大時，這份寫法會太慢，沒有辦法通過題目的完整限制。
所有變數
n：陣列長度ans：good subarray 的數量s：目前子陣列中出現過的數字集合now：目前子陣列所有元素的 bitwise OR 值
🪜 主要流程步驟
1. 先枚舉每個子陣列的起點 i
for (int i = 0; i < n; i++) {
我先固定左邊界 i，接著去看所有從
i 開始的子陣列。
2. 每次固定一個新起點時，重新準備集合和目前 OR 值
set<int> s;
int now = nums[i];
這裡：
s用來記目前這段子陣列中有哪些值now用來記目前這段子陣列的 OR 值
因為接下來我要從
i 一路往右擴，所以每換一個新的起點，都要重新開始。
3. 枚舉終點 j，讓子陣列從 [i..i] 一路擴到
[i..n-1]
for (int j = i; j < n; j++) {
這裡的意思是：
- 先看只包含一個元素的子陣列
[i..i] - 再看
[i..i+1] - 再看
[i..i+2] - 一路擴到最後
這樣就能把所有以 i 為左端點的子陣列都檢查到。
4. 更新目前子陣列的 OR 值，並把新元素放進集合
now = now | nums[j];
s.insert(nums[j]);
每次把右端點擴到 j 時：
now = now | nums[j]
-
表示把
nums[j]這個新元素一起納入目前子陣列的 OR s.insert(nums[j])
- 表示把這個值記進目前子陣列出現過的元素集合
這樣我就同時維護了：
- 整段的 OR
- 整段有哪些元素
5. 如果目前 OR 值有出現在子陣列裡，這段就是 good subarray
if (s.count(now)) {
ans++;
}
題目要的條件就是：
- 子陣列整段 OR 的結果
- 必須等於子陣列中的某個元素
而 s.count(now) 就是在問：
- 目前這段子陣列裡，有沒有出現
now這個值
如果有，代表這段子陣列符合題意，答案就加一。
6. 最後回傳 ans
return ans;
當所有起點、終點都枚舉完後，ans 就是 good subarray
的總數。
7. 這份寫法的問題在哪裡
這份程式邏輯上是直接照題意做，所以單看想法是很直觀的。
但它的時間複雜度太高：
- 外層枚舉起點
- 內層枚舉終點
- 中間還有
set操作
因此整體會接近 O(n^2 log n)。
而題目 n 可以到 10^5，所以這份寫法會超時。
也就是說，這比較像是我在比賽時先寫出的暴力檢查版本，能正確描述 good subarray 的判斷方式，但還不是最終能通過完整測資的做法。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n^2 log n)
共有 O(n^2) 個子陣列需要檢查，而
set 的插入與查詢是 O(log n)。
- 空間複雜度：
O(n)
對每個固定起點，set 最多可能存到
O(n) 個元素。
💻 程式碼實作
class Solution {
public:
long long countGoodSubarrays(vector<int>& nums) {
int n = nums.size();
long long ans = 0;
for (int i = 0; i < n; i++) {
set<int> s;
int now = nums[i];
for (int j = i; j < n; j++) {
now = now | nums[j];
s.insert(nums[j]);
if (s.count(now)) {
ans++;
}
}
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/contest/weekly-contest-494/problems/count-good-subarrays/