文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 超時解
    • 2.2 正解

1. 題目

我們有一個非負整數數組 A。

對于每個（連續的）子數組 B = [A[i], A[i+1], ..., A[j]] （ i <= j），我們對 B 中的每個元素進行按位或操作，獲得結果 A[i] | A[i+1] | ... | A[j]。

返回可能結果的數量。 （多次出現的結果在最終答案中僅計算一次。）

示例 1： 輸入：[0] 輸出：1 解釋： 只有一個可能的結果 0 。示例 2： 輸入：[1,1,2] 輸出：3 解釋： 可能的子數組為 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。 產生的結果為 1，1，2，1，3，3 。 有三個唯一值，所以答案是 3 。示例 3： 輸入：[1,2,4] 輸出：6 解釋： 可能的結果是 1，2，3，4，6，以及 7 。提示： 1 <= A.length <= 50000 0 <= A[i] <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 超時解

class Solution { // 超時 public:int subarrayBitwiseORs(vector<int>& arr) {int n = arr.size();unordered_set<int> a, b, ans;for(int i = 0; i < n; ++i){b.clear();b.insert(arr[i]);for(auto it = a.begin(); it != a.end(); ++it){b.insert(*it|arr[i]);}a.swap(b);for(auto i : a)ans.insert(i);}return ans.size();} };

2.2 正解

• 上面解法忽略了一個條件，| 操作 數字不會減小，當 區間 [j, i] | 操作的結果 == [j, i-1] 的結果，那么 [j-1, i]，[j-2, i]等往前的都不需要計算了，都是一樣的結果，A[i] 的貢獻 被 區間 [j, i-1] 掩蓋了

class Solution { public:int subarrayBitwiseORs(vector<int>& arr) {int n = arr.size();unordered_set<int> ans;for(int i = 0; i < n; ++i)//以 i 為右端點{ans.insert(arr[i]);for(int j = i-1; j >= 0; --j) // j 為左端點{if((arr[j]|arr[i])==arr[j])break;//arr[j] 存儲的是 [j, i-1] 的區間 | 和arr[j] |= arr[i]; //現在 arr[j] 存儲的是 [j, i] 的區間 | 和ans.insert(arr[j]);}}return ans.size();} };

1008 ms 95.7 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 898. 子数组按位或操作（前缀和思想）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。