2026-07-12：达到目标异或值的最少删除次数。用go语言，给定一个整数数组 nums 和一个整数 target。 你可以从 nums 里删除任意多个元素（也可以一个都不删）。删除之后，剩下的元素

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计算数组最大值的二进制位数确定状态空间大小先找出数组中最大数字maxVal用bits.Len获取maxVal二进制所占位数m状态数组长度为1 m2的m次方代表所有可能出现的异或结果提前判断边界若最大能覆盖的异或值域上限1m都小于 target直接返回-1不可能凑出目标值。步骤2初始化DP状态数组ff[xorVal]的含义能凑出异或值为xorVal的子集最多包含多少个元素。分配长度为1m的数组f全部初始化为极小值math.MinInt代表该异或值暂时无法构造f[0] 0空子集异或为0包含0个元素是初始合法状态。步骤3遍历数组每个数字逐维更新DP01背包异或DP这是标准01背包型异或动态规划每个数字只有两种选择保留 / 删除。对数组中每一个数字x执行完整一轮状态更新复制当前完整DP数组f得到临时数组nfnf代表「不选当前x」的所有状态不修改原始f避免同轮重复选取同一个x遍历每一个已存在的异或状态j若f[j]是极小值说明该异或值无法构造直接跳过若选择保留当前数字x新异或值为j ^ x新子集元素数量为f[j] 1对比nf[j^x]和新数量取更大值存入nf[j^x]保证每个异或值记录最多元素个数遍历完成后将临时数组nf赋值给f完成当前数字的决策更新。逻辑说明选/不选分支不选x状态不变直接继承复制出来的nf选x在原有异或j基础上异或x元素数量1一轮循环同时覆盖两种选择保证每个元素只选一次符合子集定义。步骤4判断是否存在合法子集计算最少删除次数读取f[target]该值是凑出异或target的最大元素数量若f[target] 0不存在任何子集满足异或等于target返回-1最少删除次数 总元素个数len(nums)− 最多保留元素f[target]。步骤5样例推演nums[1,2,3], target2数组最大值为3二进制占2位m2状态数组长度124值域0~3target2在范围内初始化 f [0, -inf, -inf, -inf]处理第一个数字 x1复制nf初始等于f遍历j0f[j]0新异或0^11数量011nf[1]更新为1更新后 f [0, 1, -inf, -inf]处理第二个数字 x2复制nf [0,1,-inf,-inf]j00^22数量1 → nf[2]1j11^23数量2 → nf[3]2更新后 f [0,1,1,2]处理第三个数字 x3复制nf [0,1,1,2]j00^33数量1当前nf[3]2更大不更新j11^32数量112比原nf[2]1更大nf[2]2j22^31数量112比原nf[1]1更大nf[1]2j33^30数量213比原nf[0]0更大nf[0]3最终 f [3, 2, 2, 2]查询f[target2] 2总长度3最少删除 3 - 2 1和样例输出一致。二、时间复杂度分析设n nums数组长度最多40S 状态总数 2^mm为数组最大值二进制位数nums[i]≤1000010000二进制约14位S ≤ 2^14 16384。完整流程时间开销求数组最大值O(n)DP数组初始化O(S)遍历每个数字n轮克隆DP数组O(S)遍历全部S个状态更新O(S)单轮总 O(S)n轮合计 O(n × S)总时间复杂度O(n × 2^m)代入上限n402^1416384总运算量约40 × 16384 655360计算量极小。三、额外空间复杂度分析DP主数组f长度 S 2^m占用 O(S)每轮临时数组nf是f的完整拷贝同时存在两份长度S的数组其余临时变量、循环变量空间可忽略总额外空间复杂度O(2^m)上限为2^1416384个int空间开销极低。Go完整代码如下packagemainimport(fmtmathmath/bitsslices)funcminRemovals(nums[]int,targetint)int{m:bits.Len(uint(slices.Max(nums)))if1mtarget{return-1}f:make([]int,1m)fori:rangef{f[i]math.MinInt}f[0]0for_,x:rangenums{nf:slices.Clone(f)forj,fj:rangef{nf[j^x]max(nf[j^x],fj1)// x 不选 or 选}fnf}iff[target]0{return-1}returnlen(nums)-f[target]}funcmain(){nums:[]int{1,2,3}target:2result:minRemovals(nums,target)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListimportmathdefminRemovals(nums:List[int],target:int)-int:# 计算 nums 中最大值需要的二进制位数max_nummax(nums)ifnumselse0mmax_num.bit_length()# 如果所有可能异或值的范围小于等于 target则无法达到 targetif(1m)target:return-1# dp数组f[state] 表示异或结果为 state 时最多能选择的数字个数# 初始化为极小值f[-math.inf]*(1m)f[0]0forxinnums:# 复制当前dp状态nff.copy()forj,fjinenumerate(f):iffj!-math.inf:# 只处理可达状态new_statej^x nf[new_state]max(nf[new_state],fj1)fnf# 如果 target 不可达iff[target]0:return-1# 最少移除数 总长度 - 最多保留数returnlen(nums)-f[target]defmain():nums[1,2,3]target2resultminRemovals(nums,target)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includealgorithm#includeclimits#includecmathusingnamespacestd;intminRemovals(vectorintnums,inttarget){// 计算 nums 中最大值需要的二进制位数intmaxNum*max_element(nums.begin(),nums.end());intm0;while((1m)maxNum){m;}// 如果所有可能异或值的范围小于等于 target则无法达到 targetif((1m)target){return-1;}// dp数组f[state] 表示异或结果为 state 时最多能选择的数字个数// 初始化为极小值intsize1m;vectorintf(size,INT_MIN);f[0]0;for(intx:nums){// 复制当前dp状态vectorintnff;for(intj0;jsize;j){if(f[j]!INT_MIN){// 只处理可达状态intnewStatej^x;nf[newState]max(nf[newState],f[j]1);}}fnf;}// 如果 target 不可达if(f[target]0){return-1;}// 最少移除数 总长度 - 最多保留数returnnums.size()-f[target];}intmain(){vectorintnums{1,2,3};inttarget2;intresultminRemovals(nums,target);coutresultendl;return0;}