1. 题目拆解从“枚举所有子数组”到“集合压缩”先把这个题目的原型摆出来给定一个非负整数数组返回所有子数组的按位或结果中不同结果的数量。很多朋友第一眼看到“所有子数组”就兴奋了枚举左端点、右端点、再做一次按位或三层循环直接上代码十秒钟写完然后一提交超时。这个题的核心考点根本不在“会不会写或运算”而在于你能不能看穿“按位或”在子数组上的单调性和状态收敛特性。暴力解法的复杂度是O(n^3)枚举区间端点O(n^2)每个区间做一次或运算O(n)n一旦到10的5次方这个量级计算量就是10的15次方量级跑完大概得等几个世纪。即便是退一步用前缀优化也只能把单次或运算降到O(1)枚举区间本身还是有O(n^2)照样炸。所以这道题本质上是在问如何利用按位或的特殊性质把“所有子数组”这个看似巨大的搜索空间压缩到一个可操作的范围。这个题目真正适合三类人准备算法面试、需要快速过一道中等偏上难度题的求职者想理解位运算单调性如何在算法题里落地的人以及做子数组类问题系列训练、希望把“滚动集合”套路吃透的人。它背后牵出的思想在“子数组按位与”“区间GCD”等问题里是一脉相通的学会这一个题相当于解锁一类题。2. 核心思路按位或的单调性凭什么能把状态压缩到32个2.1 按位或没有逆运算所以滑动窗口这条路走不通遇到子数组问题很多人第一反应是滑动窗口。子数组求和可以用滑动窗口因为加法有可逆性窗口左边收缩时直接减掉一个数即可子数组异或也可以用前缀异或因为异或的逆运算是自己。但按位或不一样它是不可逆的两个数按位或之后你没法通过右端点左移或左端点前进反推出某个bit是哪个元素贡献的。窗口左边界往右缩或值只会保持不变或者减少某些bit但你无法确定减少的是哪些bit也没法用一个“前缀或数组”直接算出任意区间的或值。这一点是题目最大的陷阱。如果你照着子数组求和的思路写滑动窗口你会发现窗口根本滑不起来左右边界没有一个明确的单调移动规则。所以正解必须换一个维度去思考——与其枚举区间不如枚举“以某个右端点结尾的所有子数组”。2.2 核心性质一个int只有32个bit或值的bit只能从0变1看一个数组 [a1, a2, a3, ..., an]固定右端点r考虑所有以a[r]结尾的子数组它们的按位或结果分别是a[r] a[r-1] | a[r] a[r-2] | a[r-1] | a[r] ...从左往右看这些值你会发现一个关键事实随着左端点不断向左扩展或值是单调不降的。更准确地说每个二进制位只会从0变成1绝不会从1变回0。新加入一个元素只可能让某个bit从0变成1或者维持现状。int总共32位每一位最多变化一次所以从a[r]这个单独元素开始一路向左扩展到a[1]或值最多只能变化32次。这意味着以a[r]结尾的所有子数组的或值集合去重之后最多只有32个左右的不同值。不是O(r)个是常数级别。整个数组n个子数组的右端点每个右端点维护32个值总状态数就是O(32n)这个量级完全可跑。2.3 滚动集合的递推公式记dp[r]为“以a[r]结尾的所有子数组按位或结果去重后的集合”。那么dp[r]可以直接由dp[r-1]推导dp[r] { a[r] } ∪ { x | a[r] | x ∈ dp[r-1] }这公式怎么理解以a[r]结尾的子数组分两类第一类是长度为1的子数组即[a[r]]或值就是a[r]第二类是长度大于1的子数组即[a[l..r]]它等于a[l..r-1]的结果再或上a[r]。而a[l..r-1]的所有可能结果恰好就是dp[r-1]里的值。所以只要拿a[r]去“或”一遍dp[r-1]里的每个值再加上a[r]本身就得到了dp[r]。把每一轮的dp[r]全部塞进一个全局的哈希集合最终这个哈希集合的大小就是答案。整个过程只需要遍历一次数组每一轮最多做32次或运算和哈希插入总复杂度O(32n)空间复杂度可以压到O(32)的滚动集合加一个全局结果集。这个递推公式是整个解法的灵魂。我见过很多写法不同的版本有的用有序集合有的用哈希集合有的甚至用bitset做压缩但万变不离其宗都是这条递推。3. 代码落地三种语言实现与参数选择3.1 Python实现哈希集合与滚动更新def subarray_bitwise_or_count(arr): # 以当前位置结尾的所有子数组或值集合 cur set() # 全局结果集合 total set() for x in arr: # 新集合上一轮每个结果与当前元素取或再加上单个元素本身 new_cur {x} for val in cur: new_cur.add(val | x) cur new_cur total | cur return len(total)这个写法里最核心的一行是new_cur {x}。很多新手会漏掉它导致长度为1的子数组丢失。然后遍历cur时逐个与x做或运算把结果加入new_cur。这里必须用一个新集合去接结果不能直接在cur上边遍历边修改否则迭代器会出问题而且会污染本轮的状态。实测下来直接原地修改会漏掉“上一轮集合元素之间互相组合”的假象实际上只要在遍历时先快照一份旧集合再改也能跑对但用新集合更干净。3.2 C实现unordered_set的玄学与优化#include vector #include unordered_set using namespace std; int subarrayBitwiseORs(vectorint arr) { unordered_setint cur; unordered_setint total; for (int x : arr) { unordered_setint next; next.insert(x); for (int val : cur) { next.insert(val | x); } cur move(next); for (int val : cur) { total.insert(val); } } return total.size(); }C用unordered_set时有个性能小技巧cur的容量在上限32附近每次重建next再move进来避免反复hash扩容。有人好奇为什么不用setset的红黑树节点开销大而且我们根本不需要有序性unordered_set平均O(1)插入更合适。哈希函数对整数有默认的identity映射这个场景下分布不错实测碰撞很少。3.3 复杂度对照与暴力法的差距方案时间复杂度空间复杂度n50000时估算暴力枚举逐位或O(n^3)O(1)约1.25e14次运算不可行前缀或枚举区间O(n^2)O(n)约2.5e9次运算依然不可行滚动集合O(32n)O(32)到O(32n)约160万次运算毫秒级前缀或的思路再提一句虽然可以用前缀或数组把任意区间或值算成O(1)但枚举全部区间依然是O(n^2)。所以真正的瓶颈不是“计算单个区间的或值”而是“合法区间的数量太多”。滚动集合的巧妙之处在于它压根不去枚举区间而是把相同或值的区间压缩成一个代表利用bit位数有限这个天花板把区间数量从n^2压到了32n。4. 边界测试与性能实测记录4.1 边界场景逐项验证我写完之后习惯性做了一组边界测试这里挑几个典型的记录一下。空数组题目一般约束n在1以上但如果n0上面的代码会正常返回0total为空集。单元素数组[0]cur {0}total {0}答案1。这里注意0本身也算一个合法结果。全零数组[0, 0, 0, ..., 0]每个位置cur {0}最终答案恒为1。如果你发现答案不是1那一定是在插入重复值时没去重。严格递增的2的幂数组[1, 2, 4, 8, ...]每个位置的cur大小会逐渐变大。到第33个元素时cur里有33个值吗其实不会因为按位或最多32bit到第33个元素时bit已经全部占满再插入新的或值只会得到同一个全1结果集合容量被压住。这个用例能直观验证“32”这个上限的作用。大数值边界[2147483647, 2147483647]两个最大int做或结果还是2147483647集合容量为1。注意别用int存负数场景这个题严格要求非负数组如果输入有负数C的int按位或对有符号数行为复杂答案也会变。4.2 随机大数组压测我用n50000的随机非负数组做压测Python版本耗时大约60ms左右C版本开启O2优化后耗时在10ms以内。这个性能完全能过LeetCode的时限要求而且内存占用也很低全局结果集在最坏情况下也不会超过32n个元素约为160万用哈希集合管理毫无压力。压测中有个有趣的现象随机数组的cur大小很少真的顶到32通常稳定在10到20之间。只有精心构造的递增幂次数组才会逼近上限。这也解释了为什么题目里n可以给到10^5因为实际常数比理论上限还要小。5. 踩坑实录这五个问题我替你先踩过了5.1 问题一忘记更新全局集合第一次写的时候我只维护了cur最后直接返回len(cur)结果答案偏小。因为cur只保存“以最后一个元素结尾”的或值而题目要求的是所有子数组前面那些子数组的结果全丢了。正确做法是每一轮把cur并入total或者直接在循环内把next的每个值插入总集合。这个错误很隐蔽因为小数组测试时往往最后一轮的cur恰好包含了部分历史值大数组一跑就露馅。5.2 问题二在迭代中修改集合Python里如果你写for val in cur: cur.add(val | x)大概率会报RuntimeError: Set changed size during iteration。即使你机灵地改成for val in list(cur)虽然不报错但新添加的值又会被当成旧值再取一次或虽然结果不会错——因为(val | x) | x等于val | x——但白白浪费时间。最好的习惯还是新建集合逻辑清晰。5.3 问题三以为可以像前缀和一样用数组映射有朋友问能不能用vectorbool或bitset标记所有出现的或值因为或值范围是[0, 2^32)直接数组映射不现实。除非题目明确数值范围很小否则哈希集合就是正解。如果确实想优化Python可以用int的bit位来标记C用std::bitset132内存又太大所以哈希集合是最平衡的选择。5.4 问题四复杂度分析写成O(n^2)面试时被追问复杂度如果你只说“遍历n每轮遍历cur”面试官会继续问cur最大多大。必须答出“每个位置集合大小不超过32因为或值bit单调上升且int只有32位”或者更严格的证明固定右端点子数组或值随左端点左移而单调不降bit只增不减最多增加32次所以集合大小有界。能给到这个深度面试官基本就满意了。5.5 问题五试图用位运算“逆操作”优化有人尝试维护一个前缀或数组然后用某种差分方式计算任意区间或值这条路走不通。因为在a | b这个操作里给定a | b的结果和a无法唯一反推b信息在或运算中丢失了。对比来看前缀异或能行是因为异或的逆运算就是自己前缀和能行是因为减法存在。按位或缺少这个性质只能靠bit上限来控制状态量。6. 同类题横向对比为什么这些题都要“压缩状态”6.1 子数组按位与同样吃单调性红利如果你做过去重后的子数组按位与数量会发现套路几乎一样。按位与的性质是单调不增的bit只能从1变0所以每个右端点结尾的不同按位与结果同样不超过32个。写法就是把x | val全部替换成x val集合中每个值只会减少bit上限同样是32。一道题吃透另一道题就是送分题。6.2 子数组异或和走的是另一条路异或问题的正解是前缀异或和哈希表因为异或具有“自反性”前缀异或可以快速查询任意区间异或值。这跟按位或形成鲜明对比一个靠逆运算直接O(n)一个靠bit上限压缩状态。面试官很喜欢拿这两道题一起问考察你对运算性质的敏感度。6.3 区间GCD数量压缩的常数更大求不同子数组GCD的数量也可以用滚动集合因为每次拓展后GCD单调递减每个位置的集合大小不会超过logV个通常视为几十个。套路如出一辙递推公式是dp[r] gcd(dp[r-1], a[r]) ∪ {a[r]}。所以“滚动集合”这个思维模式一旦建立至少能覆盖三类经典子数组题。7. 一个容易被忽略的优化提前剪枝到全1在某次实际跑数据时我发现当cur集合里出现了一个值等于UINT_MAX即32位全1时无论再与什么数取或结果都不会变。于是可以在循环里加一个提前退出如果当前cur里包含全1说明这一轮之后集合不会再产生新值可以直接跳过后续大量计算。FULL (1 31) - 1 # 按题目非负int处理最高bit为0若允许unsigned则用(132)-1 # 循环内 if FULL in cur or x FULL: total.add(FULL) continue这种优化在随机数据上收益不明显因为随机数很难凑出全1但在某些专门构造large test的评测里它能避免最后一轮几百次无意义的或运算和哈希插入。另外还有一个细节当x本身是0时cur的所有值或上0还是它们自己集合基本不变但也要照常入总集合不能continue。我在实际调试中还发现一个小规律如果数组里存在某个元素本身就是全1那么答案几乎可以提前锁定为所有可能的子数组结果数量——从该元素向左和向右扩展的所有子数组或值都是全1所以全部子数组只要有跨过这个元素的结果就只能是全1。这时候只需手工计算那些完全落在它左侧或右侧的子数组结果数量。这是竞赛思路面试里提一嘴能加分但千万别在代码里过度设计。对于这个题我觉得最值得反复品味的一点是它没有要求你返回具体子数组只问“不同结果数量”。这种问法往往暗示结果种类有界是考察状态压缩能力的信号。做多了你会发现凡是问“有多少种不同XX”的子数组题大概率不是让你去一个一个枚举而是在引导你思考这个运算的收敛性。按位或在32位的天然上限就是这道题留给你的最大提示。