LeetCode 898. 子数组按位或操作

Question

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