LeetCode 898中等动态规划
子数组按位或操作 图解题解
这道题到底在问什么
给定整数数组 arr，返回所有非空子数组「按位或」结果里不同值的个数。子数组的按位或，就是把这一段里每个数全部 OR 在一起。
- 输入
- arr=[1,2,4]
- 输出
- 6 （能得到 1,2,3,4,6,7 六种）
- 输入
- arr=[0,0]
- 输出
- 1 （[0]、[0]、[0,0] 全是 0，只一种）
最优解：一步一步想明白
- 3关键直觉：按位或只会把二进制位从 0 变 1、从不清零，所以越往左扩 OR 值只增不减，种类有限，cur 始终很小（不超过 32 个）。
- 4开局：res 是最终要数的「不同 OR 值」集合，现在为空。我们从左到右，一位一位把它喂大。
- 5从第 0 位 1 开始。它前面没有元素，以它结尾的子数组就只有它自己，所以新 cur 先从空白起步。
- 6别忘了只含 1 自己的那个子数组，OR 值就是 1，也加进来。现在以第 0 位结尾的全部 OR 值都齐了。
- 7把本轮 cur 整个倒进 res，去掉重复后净增 1 个新值（1），res 涨到 1 种。
- 8轮到第 1 位 2。上一轮以第 0 位结尾的 OR 集合是 {1}，把它们每个都和 2 求一次或，就得到「多接了一个 2」的新子数组的 OR 值。
- 9拿上一轮的 1 出来，和当前的 2 逐位求或：哪一位有 1 结果就是 1。
- 102 或 1 得 3，放进新 cur。可以看到 3 的二进制位是 2 和 1 两者 1 位的并集。
- 11别忘了只含 2 自己的那个子数组，OR 值就是 2，也加进来。现在以第 1 位结尾的全部 OR 值都齐了。
- 12把本轮 cur 整个倒进 res，去掉重复后净增 2 个新值（2、3），res 涨到 3 种。
- 13轮到第 2 位 4。上一轮以第 1 位结尾的 OR 集合是 {2, 3}，把它们每个都和 4 求一次或，就得到「多接了一个 4」的新子数组的 OR 值。
- 14拿上一轮的 2 出来，和当前的 4 逐位求或：哪一位有 1 结果就是 1。
- 154 或 2 得 6，放进新 cur。可以看到 6 的二进制位是 4 和 2 两者 1 位的并集。
- 16拿上一轮的 3 出来，和当前的 4 逐位求或：哪一位有 1 结果就是 1。
- 174 或 3 得 7，放进新 cur。可以看到 7 的二进制位是 4 和 3 两者 1 位的并集。
- 18别忘了只含 4 自己的那个子数组，OR 值就是 4，也加进来。现在以第 2 位结尾的全部 OR 值都齐了。
- 19把本轮 cur 整个倒进 res，去掉重复后净增 3 个新值（4、6、7），res 涨到 6 种。
- 20轮到第 3 位 3。上一轮以第 2 位结尾的 OR 集合是 {4, 6, 7}，把它们每个都和 3 求一次或，就得到「多接了一个 3」的新子数组的 OR 值。
- 21拿上一轮的 4 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
- 223 或 4 得 7，放进新 cur。可以看到 7 的二进制位是 3 和 4 两者 1 位的并集。
- 23拿上一轮的 6 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
- 243 或 6 得 7，放进新 cur。可以看到 7 的二进制位是 3 和 6 两者 1 位的并集。
- 25拿上一轮的 7 出来，和当前的 3 逐位求或：哪一位有 1 结果就是 1。
- 263 或 7 得 7，放进新 cur。注意结果和 7 一样，说明 3 的 1 位都被 7 盖住了。
- 27别忘了只含 3 自己的那个子数组，OR 值就是 3，也加进来。现在以第 3 位结尾的全部 OR 值都齐了。
- 28本轮 cur 里的值 res 早就有了（3、7 都见过），所以 res 一个没涨，还是 6 种。这正是「去重」在起作用。
- 29全程扫完，res 里一共 6 个不同的 OR 值（1、2、3、4、6、7），答案就是 6。
⚠️ 容易写错的地方
✗ 错：硬枚举全部 O(n²) 个子数组逐段求或
✓ 对：以 i 结尾维护滚动集合 cur
逐段重算是 O(n²) 甚至更糟，n 到 5 万必超时；滚动集合让每步只做 ≤ 32 次或
✗ 错：忘了把 arr[i] 自己加入 cur
✓ 对：每轮显式 cur.add(arr[i])
长度为 1 的子数组也要算，漏了会少一批 OR 值
✗ 错：用数组而非集合存 cur
✓ 对：必须用 set 去重
相邻 OR 值常重复，用数组会让 cur 膨胀、退化成 O(n²)
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> ans;
unordered_set<int> s;
for (int x : arr) {
unordered_set<int> t;
for (int y : s) {
t.insert(x | y);
}
t.insert(x);
ans.insert(t.begin(), t.end());
s = move(t);
}
return ans.size();
}
};Java
import java.util.*;
class Solution {
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> ans = new HashSet<>();
Set<Integer> s = new HashSet<>();
for (int x : arr) {
Set<Integer> t = new HashSet<>();
for (int y : s) {
t.add(x | y);
}
t.add(x);
ans.addAll(t);
s = t;
}
return ans.size();
}
}复杂度
时间
O(n·32)
每位的 cur 集合最多 32 个不同值（OR 单调增、位数有限），扫 n 位约 32n 次或运算，近似 O(n log max)
空间
O(n·32)
res 最多存约 32n 个不同值；滚动的 cur 只占 O(32)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 子数组按位或操作 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么「子数组的和」或「子数组的积」不能照搬这套压缩？+
关键在 OR 有单调性：往左扩值只增、变化次数被位数卡死，cur 才恒小。和、积没有这种「最多变 32 次」的性质，以 i 结尾的不同前缀和可能有 O(n) 个，压不下来。
如果把按位或换成按位与，思路要变吗？+
完全对称。按位与往左扩时值单调不增、每位最多从 1 变 0 一次，同样最多约 32 种，把转移里的 | 换成 & 即可，复杂度不变。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 子数组按位或操作 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。