题目描述
思路解析
一句话答案：LeetCode 898 子数组按位或操作：只维护「以当前元素结尾的所有子数组按位或值」这一小撮集合，滚动并入总集合去重。按位或只增位、集合恒小，时间 O(n·30)、空间 O(n·30)。
按位或的不同结果，到底在数什么
给整数数组 arr，把每个非空子数组（连续一段，不能跳着取）各做一遍按位或，问有多少个不同的值。按位或就是把一段的数逐位比较，某位只要有一个是 1，结果那位就是 1。题面 arr=[1,2,4] 能或出 1、2、3、4、6、7 六个值，答案 6；arr=[0,0] 三段全为 0 只有一种，答案 1。数的是不同结果个数，不是子数组条数。
为什么把每个子数组都或一遍会超时
长度 n 的数组有 n(n+1)/2 个子数组，逼近 O(n²) 个（大 O 记号描述规模变大时运算量怎么涨）。把每段从头或到尾又各要 O(n) 次，硬枚举奔着 O(n³) 去，n 到十万扛不住。更亏的是以同一右端点结尾的段大量重叠、前半截反复重或，这些或值该攒着复用。
盯住『以当前元素结尾』的那一小撮或值
只盯以当前这个数结尾的所有子数组各自的按位或值，收进集合 cur（自动去重）。关键是 cur 永远很小：按位或有个死性子——只把二进制位从 0 变成 1，从不把 1 清回 0。固定右端点、左端点往左扩，这段的或值只增不减。题目里的数不超过 10^9，只占 30 个二进制位；或值每真变大一次至少点亮一个新位，最多点亮 30 次就涨不动了。所以以任一位置结尾，不同或值至多约 30 个——cur 恒小的根就在这。
新一轮的或值集合，凭什么只用旧集合推
滚到下一个数 x，不必重扫前面。以 x 结尾的子数组只有两类：只有 x 自己的，或值就是 x；由前一段接上 x 而来的，或值等于那段旧或值再或上 x。上一轮的 cur 正好存着以上一个数结尾的全部或值，把每个都或一遍 x、再补上 x 自己，就是新 cur：new cur = {x | y ：y 属于旧 cur} 再并上 {x}。每得一轮就并进总集合 ans（同样去重），扫完 arr，ans 的大小即答案。这套滚着推正是动态规划：把以每个位置结尾的小答案攒下来直接复用。
拿 [1,2,4] 把集合一轮轮滚出来
拿题面 arr=[1,2,4] 滚一遍，ans 起初为空。数 1：cur={1}，ans={1}。数 2：旧 cur={1}，1 或 2 得 3，再补上 2，cur={2,3}，ans 新增 2、3 成 {1,2,3}。数 4：旧 cur={2,3}，2 或 4 得 6、3 或 4 得 7，再补 4，cur={4,6,7}，ans 新增 4、6、7 成 {1,2,3,4,6,7}。扫完 ans 里正好六个值，答案 6，和题面对上。
漏掉『只含自己』那个子数组，答案为什么会少一截
每轮忘了往 cur 补上 x 自己，是最常见的写反：单个元素单独成段的或值全丢，只有一个数的输入会连它本身都数不到。复杂度上，每个位置的 cur 至多约 30 个，扫 n 个数各做一次或，时间 O(n·30)、接近线性；ans 最多攒约 30n 个值，空间 O(n·30)，cur 只占 O(30)。两个边界想清：数组全是 0 时每段或值都是 0，答案只能是 1，别数成子数组条数；各数二进制位完全错开时或值组合最多，cur 塞得最满也不超 30 个。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键直觉：按位或只会把二进制位从 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题