LeetCode 位运算高频难题合集｜好子数组统计+目标异或最少删除次数

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 解释：数组所有子数组均为好子数组，总数量为6

1.3 数据范围提示

• 1 ≤ nums.length ≤ 1e5

• 0 ≤ nums[i] ≤ 1e9

• 数据范围大，必须采用线性/线性带常数级解法，暴力枚举子数组会超时

二、核心条件转化（解题突破口）

2.1 好子数组条件拆解

设子数组区间为[l, r]，区间内所有元素按位或结果为OR_val。

题目要求：存在x ∈ nums[l..r]，使得OR_val = x。

结合按位或性质推导：

• 按位或运算只会让结果不变或增大，不会减小，因此区间按位或结果大于等于区间内任意一个元素

• 要让OR_val = x，x 必须是区间内的最大值，且区间内其余所有元素，都是x的二进制子集（即任意元素y满足y | x = x）

2.2 计数思路：贡献法（去重+唯一计数）

直接统计会出现重复计数，因此采用枚举每个位置作为子数组最左最大值的方式，每个合法好子数组只会被计数一次，保证结果无重复、无遗漏。

核心逻辑：对每个位置i，计算以nums[i]为最左最大值的合法好子数组数量，最后累加所有位置的贡献，即为总答案。

三、高效算法设计

3.1 核心预处理模块

为快速定位合法区间边界，需预处理四类关键信息，全程复杂度O(30n)，常数30对应二进制位数（1e9<2³⁰）：

1. 二进制位前缀最近位置：pre[k][i]表示位置i左侧，最近的第k位为1的下标，无则为-1

2. 二进制位后缀最近位置：nxt[k][i]表示位置i右侧，最近的第k位为1的下标，无则为n

3. 左侧第一个大于等于当前值的位置：L_ge[i]，用单调递减栈实现，保证当前元素是最左最大值

4. 右侧第一个严格大于当前值的位置：R_gt[i]，用单调递减栈实现，限制区间内无更大元素

3.2 合法边界计算

对每个位置i，nums[i]=x：

1. 左边界：排除左侧更大元素、以及不属于x二进制子集的元素，左边界为left_bad+1

2. 右边界：排除右侧更大元素、以及不属于x二进制子集的元素，右边界为right_bad-1

3. 贡献值：(i - 左边界 + 1) × (右边界 - i + 1)，仅当边界合法时累加

3.3 复杂度分析

• 时间复杂度：O(30n)，二进制位预处理+单调栈+遍历计数，均为线性带常数复杂度

• 空间复杂度：O(30n)，存储二进制位前缀后缀数组，空间可控，适配大数据范围

四、完整AC代码（注释精讲版）

fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])->int:n=len(nums)B=30# 1e9小于2^30，30位足够覆盖所有二进制位res=0# 1. 预处理：每个二进制位的前缀最近出现位置（左侧）pre=[[-1]*nfor_inrange(B)]last_pos=[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]=last_pos[k]# 更新当前元素对应二进制位的最近位置cur=nums[i]forkinrange(B):if(cur>>k)&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]# 更新当前元素对应二进制位的最近位置cur=nums[i]forkinrange(B):if(cur>>k)&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]:idx=stack.pop()R_gt[idx]=i stack.append(i)# 5. 遍历每个位置，计算合法好子数组贡献foriinrange(n):x=nums[i]left_bad=L_ge[i]right_bad=R_gt[i]# 结合二进制位，排除非子集元素forkinrange(B):# 当前元素x的第k位为0，区间内不能出现第k位为1的元素ifnot(x>>k)&1:left_bad=max(left_bad,pre[k][i])right_bad=min(right_bad,nxt[k][i])# 计算最终合法边界left=left_bad+1right=right_bad-1# 边界合法则累加贡献ifleft<=i<=right:res+=(i-left+1)*(right-i+1)returnres

五、示例逐轮验证

5.1 示例1：nums = [4,2,3]

• i=0（元素4）：贡献1，对应子数组[4]

• i=1（元素2）：贡献1，对应子数组[2]

• i=2（元素3）：贡献2，对应子数组[3]、[2,3]

• 总结果：1+1+2=4，与预期一致

5.2 示例2：nums = [1,3,1]

• i=0（元素1）：贡献1

• i=1（元素3）：贡献4

• i=2（元素1）：贡献1

• 总结果：1+4+1=6，与预期一致

六、常见误区避坑指南

• ❌ 误区1：暴力枚举所有子数组，O(n²)复杂度，n=1e5直接超时

• ❌ 误区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 ≤ 40

• 0 ≤ nums[i] ≤ 1e4，0 ≤ target ≤ 1e4

• n≤40，直接暴力枚举子集超时，需用折半搜索优化

二、核心问题转化

最少删除元素 ⇌最多保留元素，也可转化为找异或和固定的最小删除子集，结合异或核心性质推导：

1. 设数组总异或和为total_xor，保留元素异或和为target，删除元素异或和为val

2. 根据异或性质：total_xor ^ val = target，可推出val = total_xor ^ target

3. 问题等价：找到异或和为val的最小子集，子集大小即为最少删除次数

4. 特殊情况：若val=0，说明无需删除任何元素，直接返回0

三、算法思路：折半搜索（Meet-in-the-Middle）

3.1 算法核心逻辑

n≤40时，2^{40≈1e12，暴力枚举完全不可行，折半搜索将数组拆分为两半，每半最多20个元素（2}20≈1e6，可轻松枚举），再合并结果找最优解：

1. 将数组均分为前后两半，分别枚举所有子集，记录每个异或值对应的最小子集大小

2. 遍历左半子集异或值，在右半中查找匹配的异或值，使两者异或和等于val，累加子集大小

3. 取所有合法组合的最小子集大小，即为答案

3.2 详细执行步骤

1. 计算数组总异或和total_xor，推导目标删除子集异或值val=total_xor^target，val=0直接返回0

2. 拆分数组为左右两部分，mid=n//2

3. 枚举左半所有子集，用字典存储{异或值: 最小子集长度}

4. 枚举右半所有子集，同理存储字典

5. 遍历左半字典，计算所需右半异或值=val^左半异或值，存在则更新最小删除次数

6. 无合法组合返回-1，否则返回最小次数

3.3 复杂度分析

• 时间复杂度：O(2^(n/2) × n/2)，n=40时约2e7次操作，Python可轻松通过

• 空间复杂度：O(2^(n/2))，存储两半子集的异或值与长度

四、完整AC代码

fromtypingimportListclassSolution:defminRemovals(self,nums:List[int],target:int)->int:n=len(nums)# 计算数组总异或和total_xor=0fornuminnums:total_xor^=num# 推导删除子集需要的异或值val=total_xor^target# 特殊情况：无需删除ifval==0:return0# 折半拆分数组mid=n//2left_part=nums[:mid]right_part=nums[mid:]# 枚举左半所有子集，记录最小长度left_map={}formaskinrange(1<<len(left_part)):curr_xor=0cnt=0foriinrange(len(left_part)):ifmask&(1<<i):curr_xor^=left_part[i]cnt+=1# 同一异或值保留最小长度ifcurr_xorinleft_map:left_map[curr_xor]=min(left_map[curr_xor],cnt)else:left_map[curr_xor]=cnt# 枚举右半所有子集，记录最小长度right_map={}formaskinrange(1<<len(right_part)):curr_xor=0cnt=0foriinrange(len(right_part)):ifmask&(1<<i):curr_xor^=right_part[i]cnt+=1ifcurr_xorinright_map:right_map[curr_xor]=min(right_map[curr_xor],cnt)else:right_map[curr_xor]=cnt# 合并查找最小删除次数min_remove=float('inf')forxor1,size1inleft_map.items():xor2=val^xor1ifxor2inright_map:min_remove=min(min_remove,size1+right_map[xor2])# 无解返回-1，否则返回最小次数returnmin_removeifmin_remove!=float('inf')else-1

五、示例验证

5.1 示例1：nums=[1,2,3], target=2

• total_xor=1²3=0，val=0^2=2

• 左半[1,2]子集：{0:0, 1:1, 2:1, 3:2}

• 右半[3]子集：{0:0, 3:1}

• 匹配：xor1=2（size1=1），xor2=0（size2=0），总删除次数1

5.2 示例2：nums=[2,4], target=1

• total_xor=6，val=7，无匹配子集，返回-1

5.3 示例3：nums=[7], target=7

• val=0，直接返回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 解释：数组所有子数组均为好子数组，总数量为6

1.3 数据范围提示

• 1 ≤ nums.length ≤ 1e5

• 0 ≤ nums[i] ≤ 1e9

• 数据范围大，必须采用线性/线性带常数级解法，暴力枚举子数组会超时

二、核心条件转化（解题突破口）

2.1 好子数组条件拆解

设子数组区间为[l, r]，区间内所有元素按位或结果为OR_val。

题目要求：存在x ∈ nums[l..r]，使得OR_val = x。

结合按位或性质推导：

• 按位或运算只会让结果不变或增大，不会减小，因此区间按位或结果大于等于区间内任意一个元素

• 要让OR_val = x，x 必须是区间内的最大值，且区间内其余所有元素，都是x的二进制子集（即任意元素y满足y | x = x）

2.2 计数思路：贡献法（去重+唯一计数）

直接统计会出现重复计数，因此采用枚举每个位置作为子数组最左最大值的方式，每个合法好子数组只会被计数一次，保证结果无重复、无遗漏。

核心逻辑：对每个位置i，计算以nums[i]为最左最大值的合法好子数组数量，最后累加所有位置的贡献，即为总答案。

三、高效算法设计

3.1 核心预处理模块

为快速定位合法区间边界，需预处理四类关键信息，全程复杂度O(30n)，常数30对应二进制位数（1e9<2³⁰）：

1. 二进制位前缀最近位置：pre[k][i]表示位置i左侧，最近的第k位为1的下标，无则为-1

2. 二进制位后缀最近位置：nxt[k][i]表示位置i右侧，最近的第k位为1的下标，无则为n

3. 左侧第一个大于等于当前值的位置：L_ge[i]，用单调递减栈实现，保证当前元素是最左最大值

4. 右侧第一个严格大于当前值的位置：R_gt[i]，用单调递减栈实现，限制区间内无更大元素

3.2 合法边界计算

对每个位置i，nums[i]=x：

1. 左边界：排除左侧更大元素、以及不属于x二进制子集的元素，左边界为left_bad+1

2. 右边界：排除右侧更大元素、以及不属于x二进制子集的元素，右边界为right_bad-1

3. 贡献值：(i - 左边界 + 1) × (右边界 - i + 1)，仅当边界合法时累加

3.3 复杂度分析

• 时间复杂度：O(30n)，二进制位预处理+单调栈+遍历计数，均为线性带常数复杂度

• 空间复杂度：O(30n)，存储二进制位前缀后缀数组，空间可控，适配大数据范围

四、完整AC代码（注释精讲版）

fromtypingimportListclassSolution:defcountGoodSubarrays(self,nums:List[int])->int:n=len(nums)B=30# 1e9小于2^30，30位足够覆盖所有二进制位res=0# 1. 预处理：每个二进制位的前缀最近出现位置（左侧）pre=[[-1]*nfor_inrange(B)]last_pos=[-1]*Bforiinrange(n):# 先记录当前位的最近位置forkinrange(B):pre[k][i]=last_pos[k]# 更新当前元素对应二进制位的最近位置cur=nums[i]forkinrange(B):if(cur>>k)&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]# 更新当前元素对应二进制位的最近位置cur=nums[i]forkinrange(B):if(cur>>k)&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]:idx=stack.pop()R_gt[idx]=i stack.append(i)# 5. 遍历每个位置，计算合法好子数组贡献foriinrange(n):x=nums[i]left_bad=L_ge[i]right_bad=R_gt[i]# 结合二进制位，排除非子集元素forkinrange(B):# 当前元素x的第k位为0，区间内不能出现第k位为1的元素ifnot(x>>k)&1:left_bad=max(left_bad,pre[k][i])right_bad=min(right_bad,nxt[k][i])# 计算最终合法边界left=left_bad+1right=right_bad-1# 边界合法则累加贡献ifleft<=i<=right:res+=(i-left+1)*(right-i+1)returnres

五、示例逐轮验证

5.1 示例1：nums = [4,2,3]

• i=0（元素4）：贡献1，对应子数组[4]

• i=1（元素2）：贡献1，对应子数组[2]

• i=2（元素3）：贡献2，对应子数组[3]、[2,3]

• 总结果：1+1+2=4，与预期一致

5.2 示例2：nums = [1,3,1]

• i=0（元素1）：贡献1

• i=1（元素3）：贡献4

• i=2（元素1）：贡献1

• 总结果：1+4+1=6，与预期一致

六、常见误区避坑指南

• ❌ 误区1：暴力枚举所有子数组，O(n²)复杂度，n=1e5直接超时

• ❌ 误区2：未用贡献法，导致子数组重复计数，结果偏大

• ❌ 误区3：单调栈方向错误，边界计算不准，漏算或多算合法子数组

• ❌ 误区4：二进制位数设置不足，遗漏高位，导致边界判断错误

• ✅ 正确思路：牢牢抓住“按位或=区间内某元素=区间最大值+其余元素为二进制子集”核心条件，用贡献法拆分计数，配合单调栈+位预处理实现线性复杂度

七、总结

本题的核心是抽象条件具象化，将好子数组的定义转化为可计算的区间约束，再通过贡献法实现无重复计数，搭配单调栈和二进制位预处理，把复杂度压至O(30n)，完美适配大数据范围。

这类子数组计数+位运算题型，通用解题思路：先拆解位运算性质，再转化为区间约束，最后用单调栈/前缀后缀预处理快速定位边界，避免暴力枚举。本文代码逻辑严谨、注释清晰，可直接复制提交，适配所有测试用例与边界场景。