题目描述
思路解析动画文字版
关键直觉：按位或只会把二进制位从 0 变 1、从不清零，所以越往左扩 OR 值只增不减，种类有限，cur 始终很小（不超过 32 个）。
开局：res 是最终要数的「不同 OR 值」集合，现在为空。我们从左到右，一位一位把它喂大。
从第 0 位 1 开始。它前面没有元素，以它结尾的子数组就只有它自己，所以新 cur 先从空白起步。
别忘了只含 1 自己的那个子数组，OR 值就是 1，也加进来。现在以第 0 位结尾的全部 OR 值都齐了。
把本轮 cur 整个倒进 res，去掉重复后净增 1 个新值（1），res 涨到 1 种。
轮到第 1 位 2。上一轮以第 0 位结尾的 OR 集合是 {1}，把它们每个都和 2 求一次或，就得到「多接了一个 2」的新子数组的 OR 值。
拿上一轮的 1 出来，和当前的 2 逐位求或：哪一位有 1 结果就是 1。
2 或 1 得 3，放进新 cur。可以看到 3 的二进制位是 2 和 1 两者 1 位的并集。
别忘了只含 2 自己的那个子数组，OR 值就是 2，也加进来。现在以第 1 位结尾的全部 OR 值都齐了。
把本轮 cur 整个倒进 res，去掉重复后净增 2 个新值（2、3），res 涨到 3 种。
轮到第 2 位 4。上一轮以第 1 位结尾的 OR 集合是 {2, 3}，把它们每个都和 4 求一次或，就得到「多接了一个 4」的新子数组的 OR 值。
拿上一轮的 2 出来，和当前的 4 逐位求或：哪一位有 1 结果就是 1。
4 或 2 得 6，放进新 cur。可以看到 6 的二进制位是 4 和 2 两者 1 位的并集。
拿上一轮的 3 出来，和当前的 4 逐位求或：哪一位有 1 结果就是 1。
4 或 3 得 7，放进新 cur。可以看到 7 的二进制位是 4 和 3 两者 1 位的并集。
别忘了只含 4 自己的那个子数组，OR 值就是 4，也加进来。现在以第 2 位结尾的全部 OR 值都齐了。
把本轮 cur 整个倒进 res，去掉重复后净增 3 个新值（4、6、7），res 涨到 6 种。
轮到第 3 位 3。上一轮以第 2 位结尾的 OR 集合是 {4, 6, 7}，把它们每个都和 3 求一次或，就得到「多接了一个 3」的新子数组的 OR 值。
拿上一轮的 4 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
3 或 4 得 7，放进新 cur。可以看到 7 的二进制位是 3 和 4 两者 1 位的并集。
拿上一轮的 6 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
3 或 6 得 7，放进新 cur。可以看到 7 的二进制位是 3 和 6 两者 1 位的并集。
拿上一轮的 7 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
3 或 7 得 7，放进新 cur。注意结果和 7 一样，说明 3 的 1 位都被 7 盖住了。
别忘了只含 3 自己的那个子数组，OR 值就是 3，也加进来。现在以第 3 位结尾的全部 OR 值都齐了。
本轮 cur 里的值 res 早就有了（3、7 都见过），所以 res 一个没涨，还是 6 种。这正是「去重」在起作用。
全程扫完，res 里一共 6 个不同的 OR 值（1、2、3、4、6、7），答案就是 6。
边界先想清：全 0 只有一种，位完全错开时组合最多。
两个高频追问，落点都在「OR/AND 的单调性」。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def subarrayBitwiseORs(self, arr: List[int]) -> int: ans = set() s = set() for x in arr: s = {x | y for y in s} | {x} ans |= s return len(ans)复杂度
- 时间：O(n·32)，每位的 cur 集合最多 32 个不同值（OR 单调增、位数有限），扫 n 位约 32n 次或运算，近似 O(n log max)
- 空间：O(n·32)，res 最多存约 32n 个不同值；滚动的 cur 只占 O(32)
易错点
面试追问把动画讲成自己的话
追问为什么「子数组的和」或「子数组的积」不能照搬这套压缩？
追问如果把按位或换成按位与，思路要变吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
环形子数组的最大和
LeetCode 918 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题