# 0898. 子数组按位或操作
### 题目地址(898. 子数组按位或操作)
### 题目描述
```
我们有一个非负整数数组 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
```
### 前置知识
* [【西法带你学算法】一次搞定前缀和](https://lucifer.ren/blog/2020/09/27/atMostK/)
### 公司
* 暂无
### 思路
我们首先需要对问题进行分解，分解的思路和 [【西法带你学算法】一次搞定前缀和](https://lucifer.ren/blog/2020/09/27/atMostK/) 中提到的一样。这里简单介绍一下，如果还不明白的，建议看下那篇文章。
题目需要求的是所有子数组或运算后的结果的数目（去重）。一个朴素的思路是求出所有的子数组，然后对其求或，然后放到 hashset 中去重，最后返回 hashset 的大小即可。
我们可以使用固定两个端点的方式在 $O(n^2)$ 的时间计算出所有的子数组，并在 $O(n)$ 的时间求或，因此这种朴素的算法的时间复杂度是 $O(n^2 + n)$。
#### 要点 1
而由于子数组具有连续性，也就是说如果子数组 A\[i:j] 的或是 OR(i,j)。那么子数组 A\[i:j+1] 的或就是 OR(i,j) | A\[j+1]，也就是说，我们**无需重复计算 OR(i, j)**。基于这种思路，我们可以写出 $O(n)$ 的代码。
#### 要点 2
所有的子数组其实就是:
* 以索引为 0 结束的子数组
* 以索引为 1 结束的子数组
* 。。。
因此，我们可以边遍历边计算，并使用上面提到的技巧，用之前计算的结果推导下一步的结果。
算法（假设当前遍历到了索引 i）：
* 用 pres 记录上一步的子数组异或值集合，也就是**以索引 i - 1 结尾的子数组异或值集合**
* 遍历 pres，使用 pres 中的每一项和当前数进行或运算，并将结果重新放入 pres。最后别忘了把自身也放进去。
> 为了防止迭代 pres 过程改变 pres 的值，我们可以用另外一个中间临时集合承载结果。
* 将 pres 中的所有数加入 ans，其中 ans 为我们要返回的一个 hashset
### 关键点
* 子数组是连续的，有很多性质可以利用
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution(object):
def subarrayBitwiseORs(self, A):
pres = set([0])
ans = set()
for a in A:
nxt = set()
for pre in pres:
nxt.add(a | pre)
nxt.add(a)
pres = nxt
ans |= nxt
return len(ans)
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
