0898. 子数组按位或操作

题目地址(898. 子数组按位或操作)

https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/

题目描述

我们有一个非负整数数组 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

前置知识

• 【西法带你学算法】一次搞定前缀和

公司

• 暂无

思路

我们首先需要对问题进行分解，分解的思路和 【西法带你学算法】一次搞定前缀和 中提到的一样。这里简单介绍一下，如果还不明白的，建议看下那篇文章。

题目需要求的是所有子数组或运算后的结果的数目（去重）。一个朴素的思路是求出所有的子数组，然后对其求或，然后放到 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:

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)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。