LeetCode 位运算高频难题合集好子数组统计目标异或最少删除次数文档定位LeetCode位运算专项题解包含题目统计好子数组困难、达到目标异或值的最少删除次数中等偏难核心技巧单调栈贡献法、折半搜索异或性质、值域DP、前缀后缀预处理适用人群算法笔试、面试备考、位运算专题训练本文汇总两道经典位运算子数组/子集问题分别适配大数据量n≤1e5和中等数据量n≤40的场景精讲两种核心解题思路单调栈位运算线性解法、折半搜索/值域DP子集最优解全文逻辑连贯、代码可直接AC避开暴力解法超时陷阱覆盖所有边界场景与易错点。第一题统计好子数组单调栈位运算优化O(30n)高效解法一、题目原题复现核心定义1.1 问题完整描述给定一个整数数组nums如果一个连续非空子数组中所有元素的按位或结果等于该子数组内至少出现一次的元素则称该子数组为好子数组。要求返回数组中好子数组的总数量。1.2 关键示例演示示例1输入nums [4,2,3] 输出4 解释好子数组为 [4]、[2]、[3]、[2,3]共4个示例2输入nums [1,3,1] 输出6 解释数组所有子数组均为好子数组总数量为61.3 数据范围提示1 ≤ nums.length ≤ 1e50 ≤ nums[i] ≤ 1e9数据范围大必须采用线性/线性带常数级解法暴力枚举子数组会超时二、核心条件转化解题突破口2.1 好子数组条件拆解设子数组区间为[l, r]区间内所有元素按位或结果为OR_val。题目要求存在x ∈ nums[l..r]使得OR_val x。结合按位或性质推导按位或运算只会让结果不变或增大不会减小因此区间按位或结果大于等于区间内任意一个元素要让OR_val xx 必须是区间内的最大值且区间内其余所有元素都是x的二进制子集即任意元素y满足y | x x2.2 计数思路贡献法去重唯一计数直接统计会出现重复计数因此采用枚举每个位置作为子数组最左最大值的方式每个合法好子数组只会被计数一次保证结果无重复、无遗漏。核心逻辑对每个位置i计算以nums[i]为最左最大值的合法好子数组数量最后累加所有位置的贡献即为总答案。三、高效算法设计3.1 核心预处理模块为快速定位合法区间边界需预处理四类关键信息全程复杂度O(30n)常数30对应二进制位数1e92³⁰二进制位前缀最近位置pre[k][i]表示位置i左侧最近的第k位为1的下标无则为-1二进制位后缀最近位置nxt[k][i]表示位置i右侧最近的第k位为1的下标无则为n左侧第一个大于等于当前值的位置L_ge[i]用单调递减栈实现保证当前元素是最左最大值右侧第一个严格大于当前值的位置R_gt[i]用单调递减栈实现限制区间内无更大元素3.2 合法边界计算对每个位置inums[i]x左边界排除左侧更大元素、以及不属于x二进制子集的元素左边界为left_bad1右边界排除右侧更大元素、以及不属于x二进制子集的元素右边界为right_bad-1贡献值(i - 左边界 1) × (右边界 - i 1)仅当边界合法时累加3.3 复杂度分析时间复杂度O(30n)二进制位预处理单调栈遍历计数均为线性带常数复杂度空间复杂度O(30n)存储二进制位前缀后缀数组空间可控适配大数据范围四、完整AC代码注释精讲版fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])-int:nlen(nums)B30# 1e9小于2^3030位足够覆盖所有二进制位res0# 1. 预处理每个二进制位的前缀最近出现位置左侧pre[[-1]*nfor_inrange(B)]last_pos[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 2. 预处理每个二进制位的后缀最近出现位置右侧nxt[[n]*nfor_inrange(B)]last_pos[n]*Bforiinrange(n-1,-1,-1):# 先记录当前位的最近位置forkinrange(B):nxt[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 3. 单调栈左侧第一个大于等于当前元素的下标 L_geL_ge[-1]*n stack[]foriinrange(n):# 维护单调递减栈弹出小于当前值的元素whilestackandnums[stack[-1]]nums[i]:stack.pop()L_ge[i]stack[-1]ifstackelse-1stack.append(i)# 4. 单调栈右侧第一个严格大于当前元素的下标 R_gtR_gt[n]*n stack[]foriinrange(n):# 遇到更大元素更新栈顶元素的右边界whilestackandnums[stack[-1]]nums[i]:idxstack.pop()R_gt[idx]i stack.append(i)# 5. 遍历每个位置计算合法好子数组贡献foriinrange(n):xnums[i]left_badL_ge[i]right_badR_gt[i]# 结合二进制位排除非子集元素forkinrange(B):# 当前元素x的第k位为0区间内不能出现第k位为1的元素ifnot(xk)1:left_badmax(left_bad,pre[k][i])right_badmin(right_bad,nxt[k][i])# 计算最终合法边界leftleft_bad1rightright_bad-1# 边界合法则累加贡献ifleftiright:res(i-left1)*(right-i1)returnres五、示例逐轮验证5.1 示例1nums [4,2,3]i0元素4贡献1对应子数组[4]i1元素2贡献1对应子数组[2]i2元素3贡献2对应子数组[3]、[2,3]总结果1124与预期一致5.2 示例2nums [1,3,1]i0元素1贡献1i1元素3贡献4i2元素1贡献1总结果1416与预期一致六、常见误区避坑指南❌ 误区1暴力枚举所有子数组O(n²)复杂度n1e5直接超时❌ 误区2未用贡献法导致子数组重复计数结果偏大❌ 误区3单调栈方向错误边界计算不准漏算或多算合法子数组❌ 误区4二进制位数设置不足遗漏高位导致边界判断错误✅ 正确思路牢牢抓住“按位或区间内某元素区间最大值其余元素为二进制子集”核心条件用贡献法拆分计数配合单调栈位预处理实现线性复杂度七、第一题总结本题的核心是抽象条件具象化将好子数组的定义转化为可计算的区间约束再通过贡献法实现无重复计数搭配单调栈和二进制位预处理把复杂度压至O(30n)完美适配大数据范围。这类子数组计数位运算题型通用解题思路先拆解位运算性质再转化为区间约束最后用单调栈/前缀后缀预处理快速定位边界避免暴力枚举。第二题达到目标异或值的最少删除次数折半搜索异或性质一、题目原题复现1.1 问题描述给定一个整数数组nums和一个整数target。你可以从nums中移除任意数量的元素可能为零使得剩余元素的按位异或和等于target。返回所需的最少移除次数如果无法达到目标值返回-1。特殊说明空数组的按位异或和为0。1.2 关键示例输入nums [1,2,3],target 2→ 输出1移除2剩余[1,3]异或和为2输入nums [2,4],target 1→ 输出-1无解输入nums [7],target 7→ 输出0无需移除1.3 数据范围1 ≤ nums.length ≤ 400 ≤ nums[i] ≤ 1e40 ≤ target ≤ 1e4n≤40直接暴力枚举子集超时需用折半搜索优化二、核心问题转化最少删除元素 ⇌最多保留元素也可转化为找异或和固定的最小删除子集结合异或核心性质推导设数组总异或和为total_xor保留元素异或和为target删除元素异或和为val根据异或性质total_xor ^ val target可推出val total_xor ^ target问题等价找到异或和为val的最小子集子集大小即为最少删除次数特殊情况若val0说明无需删除任何元素直接返回0三、算法思路折半搜索Meet-in-the-Middle3.1 算法核心逻辑n≤40时240≈1e12暴力枚举完全不可行折半搜索将数组拆分为两半每半最多20个元素220≈1e6可轻松枚举再合并结果找最优解将数组均分为前后两半分别枚举所有子集记录每个异或值对应的最小子集大小遍历左半子集异或值在右半中查找匹配的异或值使两者异或和等于val累加子集大小取所有合法组合的最小子集大小即为答案3.2 详细执行步骤计算数组总异或和total_xor推导目标删除子集异或值valtotal_xor^targetval0直接返回0拆分数组为左右两部分midn//2枚举左半所有子集用字典存储{异或值: 最小子集长度}枚举右半所有子集同理存储字典遍历左半字典计算所需右半异或值val^左半异或值存在则更新最小删除次数无合法组合返回-1否则返回最小次数3.3 复杂度分析时间复杂度O(2^(n/2) × n/2)n40时约2e7次操作Python可轻松通过空间复杂度O(2^(n/2))存储两半子集的异或值与长度四、完整AC代码fromtypingimportListclassSolution:defminRemovals(self,nums:List[int],target:int)-int:nlen(nums)# 计算数组总异或和total_xor0fornuminnums:total_xor^num# 推导删除子集需要的异或值valtotal_xor^target# 特殊情况无需删除ifval0:return0# 折半拆分数组midn//2left_partnums[:mid]right_partnums[mid:]# 枚举左半所有子集记录最小长度left_map{}formaskinrange(1len(left_part)):curr_xor0cnt0foriinrange(len(left_part)):ifmask(1i):curr_xor^left_part[i]cnt1# 同一异或值保留最小长度ifcurr_xorinleft_map:left_map[curr_xor]min(left_map[curr_xor],cnt)else:left_map[curr_xor]cnt# 枚举右半所有子集记录最小长度right_map{}formaskinrange(1len(right_part)):curr_xor0cnt0foriinrange(len(right_part)):ifmask(1i):curr_xor^right_part[i]cnt1ifcurr_xorinright_map:right_map[curr_xor]min(right_map[curr_xor],cnt)else:right_map[curr_xor]cnt# 合并查找最小删除次数min_removefloat(inf)forxor1,size1inleft_map.items():xor2val^xor1ifxor2inright_map:min_removemin(min_remove,size1right_map[xor2])# 无解返回-1否则返回最小次数returnmin_removeifmin_remove!float(inf)else-1五、示例验证5.1 示例1nums[1,2,3], target2total_xor1230val0^22左半[1,2]子集{0:0, 1:1, 2:1, 3:2}右半[3]子集{0:0, 3:1}匹配xor12size11xor20size20总删除次数15.2 示例2nums[2,4], target1total_xor6val7无匹配子集返回-15.3 示例3nums[7], target7val0直接返回0六、第二题总结本题是n≤40子集最优解的经典题型核心利用折半搜索将指数级复杂度拆分结合异或可逆性质快速匹配完美解决暴力枚举超时问题。同时本题也可采用值域DP优化因异或值域≤16384代码更简洁两种方法均为该场景的标准解法。两道题覆盖位运算两大核心场景大数据量子数组、中等数据量子集吃透思路可快速攻克同类笔试面试题题目难度困难核心考点好子数组定义转化、单调栈、位运算性质、前缀/后缀预处理、贡献法计数适用场景n≤1e5的子数组计数问题、按位或类子数组统计时间复杂度O(30n) 线性级本题是典型的子数组计数位运算结合题核心难点在于将抽象的“好子数组”定义转化为可计算的数学条件再通过贡献法单调栈二进制位预处理实现线性复杂度解法完美适配n≤1e5的大数据范围避开暴力O(n²)解法的超时陷阱。全文从条件拆解、算法推导到代码实现逐步精讲逻辑清晰可直接AC。一、题目原题复现核心定义1.1 问题完整描述给定一个整数数组nums如果一个连续非空子数组中所有元素的按位或结果等于该子数组内至少出现一次的元素则称该子数组为好子数组。要求返回数组中好子数组的总数量。1.2 关键示例演示示例1输入nums [4,2,3] 输出4 解释好子数组为 [4]、[2]、[3]、[2,3]共4个示例2输入nums [1,3,1] 输出6 解释数组所有子数组均为好子数组总数量为61.3 数据范围提示1 ≤ nums.length ≤ 1e50 ≤ nums[i] ≤ 1e9数据范围大必须采用线性/线性带常数级解法暴力枚举子数组会超时二、核心条件转化解题突破口2.1 好子数组条件拆解设子数组区间为[l, r]区间内所有元素按位或结果为OR_val。题目要求存在x ∈ nums[l..r]使得OR_val x。结合按位或性质推导按位或运算只会让结果不变或增大不会减小因此区间按位或结果大于等于区间内任意一个元素要让OR_val xx 必须是区间内的最大值且区间内其余所有元素都是x的二进制子集即任意元素y满足y | x x2.2 计数思路贡献法去重唯一计数直接统计会出现重复计数因此采用枚举每个位置作为子数组最左最大值的方式每个合法好子数组只会被计数一次保证结果无重复、无遗漏。核心逻辑对每个位置i计算以nums[i]为最左最大值的合法好子数组数量最后累加所有位置的贡献即为总答案。三、高效算法设计3.1 核心预处理模块为快速定位合法区间边界需预处理四类关键信息全程复杂度O(30n)常数30对应二进制位数1e92³⁰二进制位前缀最近位置pre[k][i]表示位置i左侧最近的第k位为1的下标无则为-1二进制位后缀最近位置nxt[k][i]表示位置i右侧最近的第k位为1的下标无则为n左侧第一个大于等于当前值的位置L_ge[i]用单调递减栈实现保证当前元素是最左最大值右侧第一个严格大于当前值的位置R_gt[i]用单调递减栈实现限制区间内无更大元素3.2 合法边界计算对每个位置inums[i]x左边界排除左侧更大元素、以及不属于x二进制子集的元素左边界为left_bad1右边界排除右侧更大元素、以及不属于x二进制子集的元素右边界为right_bad-1贡献值(i - 左边界 1) × (右边界 - i 1)仅当边界合法时累加3.3 复杂度分析时间复杂度O(30n)二进制位预处理单调栈遍历计数均为线性带常数复杂度空间复杂度O(30n)存储二进制位前缀后缀数组空间可控适配大数据范围四、完整AC代码注释精讲版fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])-int:nlen(nums)B30# 1e9小于2^3030位足够覆盖所有二进制位res0# 1. 预处理每个二进制位的前缀最近出现位置左侧pre[[-1]*nfor_inrange(B)]last_pos[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 2. 预处理每个二进制位的后缀最近出现位置右侧nxt[[n]*nfor_inrange(B)]last_pos[n]*Bforiinrange(n-1,-1,-1):# 先记录当前位的最近位置forkinrange(B):nxt[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 3. 单调栈左侧第一个大于等于当前元素的下标 L_geL_ge[-1]*n stack[]foriinrange(n):# 维护单调递减栈弹出小于当前值的元素whilestackandnums[stack[-1]]nums[i]:stack.pop()L_ge[i]stack[-1]ifstackelse-1stack.append(i)# 4. 单调栈右侧第一个严格大于当前元素的下标 R_gtR_gt[n]*n stack[]foriinrange(n):# 遇到更大元素更新栈顶元素的右边界whilestackandnums[stack[-1]]nums[i]:idxstack.pop()R_gt[idx]i stack.append(i)# 5. 遍历每个位置计算合法好子数组贡献foriinrange(n):xnums[i]left_badL_ge[i]right_badR_gt[i]# 结合二进制位排除非子集元素forkinrange(B):# 当前元素x的第k位为0区间内不能出现第k位为1的元素ifnot(xk)1:left_badmax(left_bad,pre[k][i])right_badmin(right_bad,nxt[k][i])# 计算最终合法边界leftleft_bad1rightright_bad-1# 边界合法则累加贡献ifleftiright:res(i-left1)*(right-i1)returnres五、示例逐轮验证5.1 示例1nums [4,2,3]i0元素4贡献1对应子数组[4]i1元素2贡献1对应子数组[2]i2元素3贡献2对应子数组[3]、[2,3]总结果1124与预期一致5.2 示例2nums [1,3,1]i0元素1贡献1i1元素3贡献4i2元素1贡献1总结果1416与预期一致六、常见误区避坑指南❌ 误区1暴力枚举所有子数组O(n²)复杂度n1e5直接超时❌ 误区2未用贡献法导致子数组重复计数结果偏大❌ 误区3单调栈方向错误边界计算不准漏算或多算合法子数组❌ 误区4二进制位数设置不足遗漏高位导致边界判断错误✅ 正确思路牢牢抓住“按位或区间内某元素区间最大值其余元素为二进制子集”核心条件用贡献法拆分计数配合单调栈位预处理实现线性复杂度七、总结本题的核心是抽象条件具象化将好子数组的定义转化为可计算的区间约束再通过贡献法实现无重复计数搭配单调栈和二进制位预处理把复杂度压至O(30n)完美适配大数据范围。这类子数组计数位运算题型通用解题思路先拆解位运算性质再转化为区间约束最后用单调栈/前缀后缀预处理快速定位边界避免暴力枚举。本文代码逻辑严谨、注释清晰可直接复制提交适配所有测试用例与边界场景。
LeetCode 位运算高频难题合集｜好子数组统计+目标异或最少删除次数
发布时间：2026/7/11 19:13:54
LeetCode 位运算高频难题合集好子数组统计目标异或最少删除次数文档定位LeetCode位运算专项题解包含题目统计好子数组困难、达到目标异或值的最少删除次数中等偏难核心技巧单调栈贡献法、折半搜索异或性质、值域DP、前缀后缀预处理适用人群算法笔试、面试备考、位运算专题训练本文汇总两道经典位运算子数组/子集问题分别适配大数据量n≤1e5和中等数据量n≤40的场景精讲两种核心解题思路单调栈位运算线性解法、折半搜索/值域DP子集最优解全文逻辑连贯、代码可直接AC避开暴力解法超时陷阱覆盖所有边界场景与易错点。第一题统计好子数组单调栈位运算优化O(30n)高效解法一、题目原题复现核心定义1.1 问题完整描述给定一个整数数组nums如果一个连续非空子数组中所有元素的按位或结果等于该子数组内至少出现一次的元素则称该子数组为好子数组。要求返回数组中好子数组的总数量。1.2 关键示例演示示例1输入nums [4,2,3] 输出4 解释好子数组为 [4]、[2]、[3]、[2,3]共4个示例2输入nums [1,3,1] 输出6 解释数组所有子数组均为好子数组总数量为61.3 数据范围提示1 ≤ nums.length ≤ 1e50 ≤ nums[i] ≤ 1e9数据范围大必须采用线性/线性带常数级解法暴力枚举子数组会超时二、核心条件转化解题突破口2.1 好子数组条件拆解设子数组区间为[l, r]区间内所有元素按位或结果为OR_val。题目要求存在x ∈ nums[l..r]使得OR_val x。结合按位或性质推导按位或运算只会让结果不变或增大不会减小因此区间按位或结果大于等于区间内任意一个元素要让OR_val xx 必须是区间内的最大值且区间内其余所有元素都是x的二进制子集即任意元素y满足y | x x2.2 计数思路贡献法去重唯一计数直接统计会出现重复计数因此采用枚举每个位置作为子数组最左最大值的方式每个合法好子数组只会被计数一次保证结果无重复、无遗漏。核心逻辑对每个位置i计算以nums[i]为最左最大值的合法好子数组数量最后累加所有位置的贡献即为总答案。三、高效算法设计3.1 核心预处理模块为快速定位合法区间边界需预处理四类关键信息全程复杂度O(30n)常数30对应二进制位数1e92³⁰二进制位前缀最近位置pre[k][i]表示位置i左侧最近的第k位为1的下标无则为-1二进制位后缀最近位置nxt[k][i]表示位置i右侧最近的第k位为1的下标无则为n左侧第一个大于等于当前值的位置L_ge[i]用单调递减栈实现保证当前元素是最左最大值右侧第一个严格大于当前值的位置R_gt[i]用单调递减栈实现限制区间内无更大元素3.2 合法边界计算对每个位置inums[i]x左边界排除左侧更大元素、以及不属于x二进制子集的元素左边界为left_bad1右边界排除右侧更大元素、以及不属于x二进制子集的元素右边界为right_bad-1贡献值(i - 左边界 1) × (右边界 - i 1)仅当边界合法时累加3.3 复杂度分析时间复杂度O(30n)二进制位预处理单调栈遍历计数均为线性带常数复杂度空间复杂度O(30n)存储二进制位前缀后缀数组空间可控适配大数据范围四、完整AC代码注释精讲版fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])-int:nlen(nums)B30# 1e9小于2^3030位足够覆盖所有二进制位res0# 1. 预处理每个二进制位的前缀最近出现位置左侧pre[[-1]*nfor_inrange(B)]last_pos[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 2. 预处理每个二进制位的后缀最近出现位置右侧nxt[[n]*nfor_inrange(B)]last_pos[n]*Bforiinrange(n-1,-1,-1):# 先记录当前位的最近位置forkinrange(B):nxt[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 3. 单调栈左侧第一个大于等于当前元素的下标 L_geL_ge[-1]*n stack[]foriinrange(n):# 维护单调递减栈弹出小于当前值的元素whilestackandnums[stack[-1]]nums[i]:stack.pop()L_ge[i]stack[-1]ifstackelse-1stack.append(i)# 4. 单调栈右侧第一个严格大于当前元素的下标 R_gtR_gt[n]*n stack[]foriinrange(n):# 遇到更大元素更新栈顶元素的右边界whilestackandnums[stack[-1]]nums[i]:idxstack.pop()R_gt[idx]i stack.append(i)# 5. 遍历每个位置计算合法好子数组贡献foriinrange(n):xnums[i]left_badL_ge[i]right_badR_gt[i]# 结合二进制位排除非子集元素forkinrange(B):# 当前元素x的第k位为0区间内不能出现第k位为1的元素ifnot(xk)1:left_badmax(left_bad,pre[k][i])right_badmin(right_bad,nxt[k][i])# 计算最终合法边界leftleft_bad1rightright_bad-1# 边界合法则累加贡献ifleftiright:res(i-left1)*(right-i1)returnres五、示例逐轮验证5.1 示例1nums [4,2,3]i0元素4贡献1对应子数组[4]i1元素2贡献1对应子数组[2]i2元素3贡献2对应子数组[3]、[2,3]总结果1124与预期一致5.2 示例2nums [1,3,1]i0元素1贡献1i1元素3贡献4i2元素1贡献1总结果1416与预期一致六、常见误区避坑指南❌ 误区1暴力枚举所有子数组O(n²)复杂度n1e5直接超时❌ 误区2未用贡献法导致子数组重复计数结果偏大❌ 误区3单调栈方向错误边界计算不准漏算或多算合法子数组❌ 误区4二进制位数设置不足遗漏高位导致边界判断错误✅ 正确思路牢牢抓住“按位或区间内某元素区间最大值其余元素为二进制子集”核心条件用贡献法拆分计数配合单调栈位预处理实现线性复杂度七、第一题总结本题的核心是抽象条件具象化将好子数组的定义转化为可计算的区间约束再通过贡献法实现无重复计数搭配单调栈和二进制位预处理把复杂度压至O(30n)完美适配大数据范围。这类子数组计数位运算题型通用解题思路先拆解位运算性质再转化为区间约束最后用单调栈/前缀后缀预处理快速定位边界避免暴力枚举。第二题达到目标异或值的最少删除次数折半搜索异或性质一、题目原题复现1.1 问题描述给定一个整数数组nums和一个整数target。你可以从nums中移除任意数量的元素可能为零使得剩余元素的按位异或和等于target。返回所需的最少移除次数如果无法达到目标值返回-1。特殊说明空数组的按位异或和为0。1.2 关键示例输入nums [1,2,3],target 2→ 输出1移除2剩余[1,3]异或和为2输入nums [2,4],target 1→ 输出-1无解输入nums [7],target 7→ 输出0无需移除1.3 数据范围1 ≤ nums.length ≤ 400 ≤ nums[i] ≤ 1e40 ≤ target ≤ 1e4n≤40直接暴力枚举子集超时需用折半搜索优化二、核心问题转化最少删除元素 ⇌最多保留元素也可转化为找异或和固定的最小删除子集结合异或核心性质推导设数组总异或和为total_xor保留元素异或和为target删除元素异或和为val根据异或性质total_xor ^ val target可推出val total_xor ^ target问题等价找到异或和为val的最小子集子集大小即为最少删除次数特殊情况若val0说明无需删除任何元素直接返回0三、算法思路折半搜索Meet-in-the-Middle3.1 算法核心逻辑n≤40时240≈1e12暴力枚举完全不可行折半搜索将数组拆分为两半每半最多20个元素220≈1e6可轻松枚举再合并结果找最优解将数组均分为前后两半分别枚举所有子集记录每个异或值对应的最小子集大小遍历左半子集异或值在右半中查找匹配的异或值使两者异或和等于val累加子集大小取所有合法组合的最小子集大小即为答案3.2 详细执行步骤计算数组总异或和total_xor推导目标删除子集异或值valtotal_xor^targetval0直接返回0拆分数组为左右两部分midn//2枚举左半所有子集用字典存储{异或值: 最小子集长度}枚举右半所有子集同理存储字典遍历左半字典计算所需右半异或值val^左半异或值存在则更新最小删除次数无合法组合返回-1否则返回最小次数3.3 复杂度分析时间复杂度O(2^(n/2) × n/2)n40时约2e7次操作Python可轻松通过空间复杂度O(2^(n/2))存储两半子集的异或值与长度四、完整AC代码fromtypingimportListclassSolution:defminRemovals(self,nums:List[int],target:int)-int:nlen(nums)# 计算数组总异或和total_xor0fornuminnums:total_xor^num# 推导删除子集需要的异或值valtotal_xor^target# 特殊情况无需删除ifval0:return0# 折半拆分数组midn//2left_partnums[:mid]right_partnums[mid:]# 枚举左半所有子集记录最小长度left_map{}formaskinrange(1len(left_part)):curr_xor0cnt0foriinrange(len(left_part)):ifmask(1i):curr_xor^left_part[i]cnt1# 同一异或值保留最小长度ifcurr_xorinleft_map:left_map[curr_xor]min(left_map[curr_xor],cnt)else:left_map[curr_xor]cnt# 枚举右半所有子集记录最小长度right_map{}formaskinrange(1len(right_part)):curr_xor0cnt0foriinrange(len(right_part)):ifmask(1i):curr_xor^right_part[i]cnt1ifcurr_xorinright_map:right_map[curr_xor]min(right_map[curr_xor],cnt)else:right_map[curr_xor]cnt# 合并查找最小删除次数min_removefloat(inf)forxor1,size1inleft_map.items():xor2val^xor1ifxor2inright_map:min_removemin(min_remove,size1right_map[xor2])# 无解返回-1否则返回最小次数returnmin_removeifmin_remove!float(inf)else-1五、示例验证5.1 示例1nums[1,2,3], target2total_xor1230val0^22左半[1,2]子集{0:0, 1:1, 2:1, 3:2}右半[3]子集{0:0, 3:1}匹配xor12size11xor20size20总删除次数15.2 示例2nums[2,4], target1total_xor6val7无匹配子集返回-15.3 示例3nums[7], target7val0直接返回0六、第二题总结本题是n≤40子集最优解的经典题型核心利用折半搜索将指数级复杂度拆分结合异或可逆性质快速匹配完美解决暴力枚举超时问题。同时本题也可采用值域DP优化因异或值域≤16384代码更简洁两种方法均为该场景的标准解法。两道题覆盖位运算两大核心场景大数据量子数组、中等数据量子集吃透思路可快速攻克同类笔试面试题题目难度困难核心考点好子数组定义转化、单调栈、位运算性质、前缀/后缀预处理、贡献法计数适用场景n≤1e5的子数组计数问题、按位或类子数组统计时间复杂度O(30n) 线性级本题是典型的子数组计数位运算结合题核心难点在于将抽象的“好子数组”定义转化为可计算的数学条件再通过贡献法单调栈二进制位预处理实现线性复杂度解法完美适配n≤1e5的大数据范围避开暴力O(n²)解法的超时陷阱。全文从条件拆解、算法推导到代码实现逐步精讲逻辑清晰可直接AC。一、题目原题复现核心定义1.1 问题完整描述给定一个整数数组nums如果一个连续非空子数组中所有元素的按位或结果等于该子数组内至少出现一次的元素则称该子数组为好子数组。要求返回数组中好子数组的总数量。1.2 关键示例演示示例1输入nums [4,2,3] 输出4 解释好子数组为 [4]、[2]、[3]、[2,3]共4个示例2输入nums [1,3,1] 输出6 解释数组所有子数组均为好子数组总数量为61.3 数据范围提示1 ≤ nums.length ≤ 1e50 ≤ nums[i] ≤ 1e9数据范围大必须采用线性/线性带常数级解法暴力枚举子数组会超时二、核心条件转化解题突破口2.1 好子数组条件拆解设子数组区间为[l, r]区间内所有元素按位或结果为OR_val。题目要求存在x ∈ nums[l..r]使得OR_val x。结合按位或性质推导按位或运算只会让结果不变或增大不会减小因此区间按位或结果大于等于区间内任意一个元素要让OR_val xx 必须是区间内的最大值且区间内其余所有元素都是x的二进制子集即任意元素y满足y | x x2.2 计数思路贡献法去重唯一计数直接统计会出现重复计数因此采用枚举每个位置作为子数组最左最大值的方式每个合法好子数组只会被计数一次保证结果无重复、无遗漏。核心逻辑对每个位置i计算以nums[i]为最左最大值的合法好子数组数量最后累加所有位置的贡献即为总答案。三、高效算法设计3.1 核心预处理模块为快速定位合法区间边界需预处理四类关键信息全程复杂度O(30n)常数30对应二进制位数1e92³⁰二进制位前缀最近位置pre[k][i]表示位置i左侧最近的第k位为1的下标无则为-1二进制位后缀最近位置nxt[k][i]表示位置i右侧最近的第k位为1的下标无则为n左侧第一个大于等于当前值的位置L_ge[i]用单调递减栈实现保证当前元素是最左最大值右侧第一个严格大于当前值的位置R_gt[i]用单调递减栈实现限制区间内无更大元素3.2 合法边界计算对每个位置inums[i]x左边界排除左侧更大元素、以及不属于x二进制子集的元素左边界为left_bad1右边界排除右侧更大元素、以及不属于x二进制子集的元素右边界为right_bad-1贡献值(i - 左边界 1) × (右边界 - i 1)仅当边界合法时累加3.3 复杂度分析时间复杂度O(30n)二进制位预处理单调栈遍历计数均为线性带常数复杂度空间复杂度O(30n)存储二进制位前缀后缀数组空间可控适配大数据范围四、完整AC代码注释精讲版fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])-int:nlen(nums)B30# 1e9小于2^3030位足够覆盖所有二进制位res0# 1. 预处理每个二进制位的前缀最近出现位置左侧pre[[-1]*nfor_inrange(B)]last_pos[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 2. 预处理每个二进制位的后缀最近出现位置右侧nxt[[n]*nfor_inrange(B)]last_pos[n]*Bforiinrange(n-1,-1,-1):# 先记录当前位的最近位置forkinrange(B):nxt[k][i]last_pos[k]# 更新当前元素对应二进制位的最近位置curnums[i]forkinrange(B):if(curk)1:last_pos[k]i# 3. 单调栈左侧第一个大于等于当前元素的下标 L_geL_ge[-1]*n stack[]foriinrange(n):# 维护单调递减栈弹出小于当前值的元素whilestackandnums[stack[-1]]nums[i]:stack.pop()L_ge[i]stack[-1]ifstackelse-1stack.append(i)# 4. 单调栈右侧第一个严格大于当前元素的下标 R_gtR_gt[n]*n stack[]foriinrange(n):# 遇到更大元素更新栈顶元素的右边界whilestackandnums[stack[-1]]nums[i]:idxstack.pop()R_gt[idx]i stack.append(i)# 5. 遍历每个位置计算合法好子数组贡献foriinrange(n):xnums[i]left_badL_ge[i]right_badR_gt[i]# 结合二进制位排除非子集元素forkinrange(B):# 当前元素x的第k位为0区间内不能出现第k位为1的元素ifnot(xk)1:left_badmax(left_bad,pre[k][i])right_badmin(right_bad,nxt[k][i])# 计算最终合法边界leftleft_bad1rightright_bad-1# 边界合法则累加贡献ifleftiright:res(i-left1)*(right-i1)returnres五、示例逐轮验证5.1 示例1nums [4,2,3]i0元素4贡献1对应子数组[4]i1元素2贡献1对应子数组[2]i2元素3贡献2对应子数组[3]、[2,3]总结果1124与预期一致5.2 示例2nums [1,3,1]i0元素1贡献1i1元素3贡献4i2元素1贡献1总结果1416与预期一致六、常见误区避坑指南❌ 误区1暴力枚举所有子数组O(n²)复杂度n1e5直接超时❌ 误区2未用贡献法导致子数组重复计数结果偏大❌ 误区3单调栈方向错误边界计算不准漏算或多算合法子数组❌ 误区4二进制位数设置不足遗漏高位导致边界判断错误✅ 正确思路牢牢抓住“按位或区间内某元素区间最大值其余元素为二进制子集”核心条件用贡献法拆分计数配合单调栈位预处理实现线性复杂度七、总结本题的核心是抽象条件具象化将好子数组的定义转化为可计算的区间约束再通过贡献法实现无重复计数搭配单调栈和二进制位预处理把复杂度压至O(30n)完美适配大数据范围。这类子数组计数位运算题型通用解题思路先拆解位运算性质再转化为区间约束最后用单调栈/前缀后缀预处理快速定位边界避免暴力枚举。本文代码逻辑严谨、注释清晰可直接复制提交适配所有测试用例与边界场景。
