2026-07-12：达到目标异或值的最少删除次数。用go语言，给定一个整数数组 nums 和一个整数 target。
你可以从 nums 里删除任意多个元素（也可以一个都不删）。删除之后，剩下的元素组成一个新数组。要求：这个新数组所有元素的“按位异或”结果必须等于 target。
请计算达到上述条件所需的最少删除次数。如果无论怎么删除都无法让剩余元素的按位异或结果等于 target，则返回 -1。
注意：如果你把数组删空，那么空数组的按位异或结果规定为 0。
1 <= nums.length <= 40。
0 <= nums[i] <= 10000。
0 <= target <= 10000。
输入： nums = [1,2,3], target = 2。
输出： 1。
解释：
移除 nums[1] = 2 后剩余 [nums[0], nums[2]] = [1, 3]。
[1, 3] 的异或和为 2，等于 target。
无法在少于 1 次移除的情况下达到异或和 = 2，因此答案为 1。
题目来自力扣3877。
一、代码整体思路分步拆解 步骤1：计算数组最大值的二进制位数，确定状态空间大小
1. 先找出数组中最大数字
maxVal；2. 用
bits.Len获取maxVal二进制所占位数m；3. 状态数组长度为
1 << m（2的m次方），代表所有可能出现的异或结果；4. 提前判断边界：若最大能覆盖的异或值域上限
1<都小于 target，直接返回-1（不可能凑出目标值）。
f[xorVal]的含义：能凑出异或值为xorVal的子集，最多包含多少个元素。
1. 分配长度为
1<的数组f；2. 全部初始化为极小值
math.MinInt，代表该异或值暂时无法构造；3.
f[0] = 0：空子集异或为0，包含0个元素，是初始合法状态。
这是标准01背包型异或动态规划，每个数字只有两种选择：保留 / 删除。
对数组中每一个数字x，执行完整一轮状态更新：
1. 复制当前完整DP数组
f得到临时数组nf，nf代表「不选当前x」的所有状态（不修改原始f，避免同轮重复选取同一个x）；2. 遍历每一个已存在的异或状态
j：
• 若
f[j]是极小值，说明该异或值无法构造，直接跳过；• 若选择保留当前数字x，新异或值为
j ^ x，新子集元素数量为f[j] + 1；• 对比
nf[j^x]和新数量，取更大值存入nf[j^x]：保证每个异或值记录最多元素个数；
3. 遍历完成后，将临时数组nf赋值给f，完成当前数字的决策更新。
逻辑说明（选/不选分支）
• 不选x：状态不变，直接继承复制出来的nf；
• 选x：在原有异或j基础上异或x，元素数量+1；
一轮循环同时覆盖两种选择，保证每个元素只选一次，符合子集定义。
1. 读取
f[target]：该值是凑出异或target的最大元素数量；2. 若
f[target] < 0：不存在任何子集满足异或等于target，返回-1；3. 最少删除次数 = 总元素个数
len(nums)− 最多保留元素f[target]。
1. 数组最大值为3，二进制占2位，m=2，状态数组长度
1<<2=4，值域0~3，target=2在范围内；2. 初始化 f = [0, -inf, -inf, -inf]；
3. 处理第一个数字 x=1：
• 复制nf初始等于f；
• 遍历j=0，f[j]=0；新异或0^1=1，数量0+1=1；nf[1]更新为1；
• 更新后 f = [0, 1, -inf, -inf]；
4. 处理第二个数字 x=2：
• 复制nf = [0,1,-inf,-inf]；
• j=0：0^2=2，数量1 → nf[2]=1；
• j=1：1^2=3，数量2 → nf[3]=2；
• 更新后 f = [0,1,1,2]；
5. 处理第三个数字 x=3：
• 复制nf = [0,1,1,2]；
• j=0：0^3=3，数量1，当前nf[3]=2更大，不更新；
• j=1：1^3=2，数量1+1=2，比原nf[2]=1更大，nf[2]=2；
• j=2：2^3=1，数量1+1=2，比原nf[1]=1更大，nf[1]=2；
• j=3：3^3=0，数量2+1=3，比原nf[0]=0更大，nf[0]=3；
• 最终 f = [3, 2, 2, 2]；
6. 查询f[target=2] = 2，总长度3；最少删除 = 3 - 2 = 1，和样例输出一致。
二、时间复杂度分析
设：
• n = nums数组长度（最多40）
• S = 状态总数 = 2^m，m为数组最大值二进制位数；nums[i]≤10000，10000二进制约14位，S ≤ 2^14 = 16384。
完整流程时间开销：
1. 求数组最大值：O(n)；
2. DP数组初始化：O(S)；
3. 遍历每个数字（n轮）：
• 克隆DP数组：O(S)；
• 遍历全部S个状态更新：O(S)；
单轮总 O(S)，n轮合计 O(n × S)；
总时间复杂度：O(n × 2^m)
代入上限：n=40，2^14=16384，总运算量约40 × 16384 = 655360，计算量极小。
三、额外空间复杂度分析
1. DP主数组f：长度 S = 2^m，占用 O(S)；
2. 每轮临时数组nf是f的完整拷贝，同时存在两份长度S的数组；
3. 其余临时变量、循环变量空间可忽略；
总额外空间复杂度：O(2^m)
上限为2^14=16384个int，空间开销极低。
Go完整代码如下：
package main
import (
"fmt"
"math"
"math/bits"
"slices"
)func minRemovals(nums []int, target int)int {
m := bits.Len(uint(slices.Max(nums)))
if1<
return -1
}
f := make ([] int , 1 <
for i := range f {
f[i] = math.MinInt
}
f[ 0 ] = 0
for _, x := range nums {
nf := slices.Clone(f)
for j, fj := range f {
nf[j^x] = max(nf[j^x], fj+ 1 ) // x 不选 or 选
}
f = nf
}
if f[target] < 0 {
return -1
}
return len (nums) - f[target]
}
func main() {
nums := [] int { 1 , 2 , 3 }
target := 2
result := minRemovals(nums, target)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
import math
def minRemovals(nums: List[int], target: int) -> int:
# 计算 nums 中最大值需要的二进制位数
max_num = max(nums) if nums else0
m = max_num.bit_length()
# 如果所有可能异或值的范围小于等于 target，则无法达到 target
if (1 << m) <= target:
return-1
# dp数组，f[state] 表示异或结果为 state 时最多能选择的数字个数
# 初始化为极小值
f = [-math.inf] * (1 << m)
f[0] = 0
for x in nums:
# 复制当前dp状态
nf = f.copy()
for j, fj in enumerate(f):
if fj != -math.inf: # 只处理可达状态
new_state = j ^ x
nf[new_state] = max(nf[new_state], fj + 1)
f = nf
# 如果 target 不可达
if f[target] < 0:
return-1
# 最少移除数 = 总长度 - 最多保留数
returnlen(nums) - f[target]
def main():
nums = [1, 2, 3]
target = 2
result = minRemovals(nums, target)
print(result)if __name__ == "__main__":
main()
C++完整代码如下：
using namespace std;
int minRemovals(vector& nums, int target) {
// 计算 nums 中最大值需要的二进制位数
int maxNum = *max_element(nums.begin(), nums.end());
int m = 0;
while ((1 << m) <= maxNum) {
m++;
}
// 如果所有可能异或值的范围小于等于 target，则无法达到 target
if ((1 << m) <= target) {
return-1;
}
// dp数组，f[state] 表示异或结果为 state 时最多能选择的数字个数
// 初始化为极小值
int size = 1 << m;
vector f(size, INT_MIN);
f[0] = 0;
for (int x : nums) {
// 复制当前dp状态
vector nf = f;
for (int j = 0; j < size; j++) {
if (f[j] != INT_MIN) { // 只处理可达状态
int newState = j ^ x;
nf[newState] = max(nf[newState], f[j] + 1);
}
}
f = nf;
}
// 如果 target 不可达
if (f[target] < 0) {
return-1;
}
// 最少移除数 = 总长度 - 最多保留数
return nums.size() - f[target];
}int main() {
vector nums = {1, 2, 3};
int target = 2;
int result = minRemovals(nums, target);
cout << result << endl;
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴