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：计算数组最大值的二进制位数，确定状态空间大小

1. 先找出数组中最大数字maxVal；

2. 用bits.Len获取maxVal二进制所占位数m；

3. 状态数组长度为1 << m（2的m次方），代表所有可能出现的异或结果；

4. 提前判断边界：若最大能覆盖的异或值域上限1<
都小于 target，直接返回-1（不可能凑出目标值）。

步骤2：初始化DP状态数组f

f[xorVal]的含义：能凑出异或值为xorVal的子集，最多包含多少个元素。

1. 分配长度为1<
的数组f；

2. 全部初始化为极小值math.MinInt，代表该异或值暂时无法构造；

3.f[0] = 0：空子集异或为0，包含0个元素，是初始合法状态。

步骤3：遍历数组每个数字，逐维更新DP（01背包异或DP）

这是标准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；
一轮循环同时覆盖两种选择，保证每个元素只选一次，符合子集定义。

步骤4：判断是否存在合法子集，计算最少删除次数

1. 读取f[target]：该值是凑出异或target的最大元素数量；

2. 若f[target] < 0：不存在任何子集满足异或等于target，返回-1；

3. 最少删除次数 = 总元素个数len(nums)− 最多保留元素f[target]。

步骤5：样例推演（nums=[1,2,3], target=2）

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助力您的未来发展。