---

0898. 子数组按位或操作

• 标签：位运算、数组、动态规划
• 难度：中等

题目链接

• 0898. 子数组按位或操作 - 力扣

题目大意

描述：

给定一个整数数组 $arr$。

要求：

返回所有 $arr$ 的非空子数组的不同按位或的数量。

说明：

• 「子数组的按位或」是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。
• 「子数组」是数组内连续的非空元素序列。
• $1 \le nums.length \le 5 \times 10^{4}$。
• $0 \le nums[i] \le 10^{9}$。

示例：

• 示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0 。

• 示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

解题思路

思路 1：动态规划 + 哈希表

这道题要求计算所有子数组的按位或结果的不同值数量。

关键观察：

• 对于以位置 $i$ 结尾的所有子数组，它们的按位或结果最多只有 $O(\log C)$ 个不同值（$C$ 是数组中的最大值）。
• 原因：按位或操作只会增加 1 的位数，而整数最多有 $\log C$ 位。

算法步骤：

1. 使用集合 $result$ 存储所有不同的按位或结果。
2. 使用集合 $cur$ 存储以当前位置结尾的所有子数组的按位或结果。
3. 遍历数组：
   • 对于每个元素 $arr[i]$，计算它与 $cur$ 中所有值的按位或结果，加上它本身。
   • 更新 $cur$ 为新的按位或结果集合。
   • 将 $cur$ 中的所有值加入 $result$。
4. 返回 $result$ 的大小。

思路 1：代码

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        result = set()  # 存储所有不同的按位或结果
        cur = set()     # 存储以当前位置结尾的所有子数组的按位或结果
        
        for num in arr:
            # 计算以当前元素结尾的所有子数组的按位或结果
            cur = {num | x for x in cur} | {num}
            # 将结果加入总集合
            result |= cur
        
        return len(result)

思路 1：复杂度分析

• 时间复杂度：$O(n \log C)$，其中 $n$ 是数组的长度，$C$ 是数组中的最大值。对于每个元素，$cur$ 集合的大小最多为 $O(\log C)$。
• 空间复杂度：$O(n \log C)$，需要存储所有不同的按位或结果。