2026-02-28：按位异或非零的最长子序列。用go语言，给定一个整数数组 nums，要求从中选出一个非空子序列（保持原有相对次序，可删去若干

福大大架构师每日一题

发布于 2026-03-04 19:51:08

650

2026-02-28：按位异或非零的最长子序列。用go语言，给定一个整数数组 nums，要求从中选出一个非空子序列（保持原有相对次序，可删去若干元素），使得把该子序列所有元素按二进制位进行异或运算后的结果不为 0。返回满足这一条件的子序列中长度最大的值；如果没有任何子序列的异或结果为非零，则返回 0。

1 <= nums.length <= 100000。

0 <= nums[i] <= 1000000000。

输入： nums = [2,3,4]。

输出： 3。

解释：

最长子序列是 [2, 3, 4]。按位异或计算为 2 XOR 3 XOR 4 = 5，它是非零的。

题目来自力扣3702。

一、代码执行的详细过程

这段代码的核心思路是不直接枚举所有子序列（否则会超时），而是通过数学性质推导最优解，具体步骤如下：

步骤1：初始化核心变量

首先定义两个关键变量：

• sum：用于累加数组中所有元素的和，初始值为0；
• xor：用于计算数组中所有元素的异或结果，初始值为0（异或的初始值为0，因为0异或任何数等于该数本身）。

步骤2：遍历数组，计算总和与整体异或值

遍历数组nums中的每一个元素x：

• 把x加到sum中（sum += x），目的是判断数组是否全为0；
• 把x与当前xor做异或运算（xor ^= x），得到整个数组所有元素的异或结果。

以输入nums = [2,3,4]为例：

• 遍历2：sum=2，xor=2；
• 遍历3：sum=5，xor=2^3=1；
• 遍历4：sum=9，xor=1^4=5；最终sum=9，xor=5。

步骤3：判断数组是否全为0（特殊情况1）

检查sum是否等于0：

• 如果sum == 0，说明数组中所有元素都是0（因为0是唯一累加和为0的非负数）。此时任何子序列的异或结果都是0（0异或0还是0），因此返回0（没有符合条件的子序列）。
• 本例中sum=9≠0，跳过此逻辑。

步骤4：初始化最优解，处理整体异或为0的情况（特殊情况2）

首先将最优解ans初始化为数组的长度len(nums)（即默认整个数组是最优解）：

• 如果整个数组的异或结果xor == 0：说明整个数组的异或结果为0，不符合要求。此时需要去掉任意一个非零元素（因为数组不全为0，必然存在非零元素），这样剩下的子序列长度为len(nums)-1，且异或结果一定非0（原数组异或为0，去掉一个元素后，异或结果等于该元素本身，而非零元素的异或结果不为0），因此ans需要减1。
• 如果xor != 0：说明整个数组的异或结果非0，直接保留ans = len(nums)即可。

本例中xor=5≠0，因此ans保持为3。

步骤5：返回结果

最终返回ans，本例中返回3，与题目预期一致。

二、补充说明（关键逻辑的底层原理）

1. 为什么“整个数组异或为0时，去掉一个非零元素就可行”？假设数组所有元素异或为a1^a2^...^an = 0，则a1^a2^...^a(n-1) = an。如果an是非零元素，那么前n-1个元素的异或结果就是an（非0），因此子序列长度为n-1是符合要求的，且这是最长的可能（因为n长度的子序列不符合，n-1是次长）。
2. 为什么不需要考虑更短的子序列？我们的目标是“最长”子序列，因此优先尝试最长的可能（整个数组），只有当整个数组不符合时，才退而求其次（长度-1），无需考虑更短的情况。

三、时间复杂度与空间复杂度分析

1. 时间复杂度

代码中仅执行了一次遍历数组的操作（遍历所有元素计算sum和xor），遍历的时间复杂度为O(n)（n是数组长度）；其余操作（变量初始化、条件判断、赋值）都是O(1)的常数操作。因此总的时间复杂度为O(n)。

2. 额外空间复杂度

代码中仅定义了sum、xor、ans等有限个变量，没有使用与数组长度相关的额外空间（如切片、哈希表等）。因此总的额外空间复杂度为O(1)（常数级空间）。

总结

1. 核心逻辑：优先尝试整个数组作为解，仅在整个数组异或为0时缩短1位，全0数组直接返回0；
2. 时间复杂度：O(n)（仅遍历数组一次）；
3. 空间复杂度：O(1)（仅使用常数个临时变量）。

这段代码的优势在于避开了枚举子序列的暴力解法（O(2^n)），利用异或的数学性质将时间复杂度优化到线性，能高效处理题目中n≤100000的输入规模。

Go完整代码如下：

package main

import (
    "fmt"
)

func longestSubsequence(nums []int)int {
    sum, xor := 0, 0
    for _, x := range nums {
        sum += x
        xor ^= x
    }
    if sum == 0 {
        return0// nums 全为 0，无解
    }

    ans := len(nums)
    if xor == 0 {
        ans-- // 去掉 nums 的一个非零元素，就可以使 xor 不为 0
    }
    return ans
}

func main() {
    nums := []int{2, 3, 4}
    result := longestSubsequence(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def longest_subsequence(nums):
    total_sum = 0
    xor_result = 0
    
    for x in nums:
        total_sum += x
        xor_result ^= x
    
    if total_sum == 0:
        return0  # nums 全为 0，无解
    
    result = len(nums)
    if xor_result == 0:
        result -= 1  # 去掉 nums 的一个非零元素，就可以使 xor 不为 0
    
    return result

def main():
    nums = [2, 3, 4]
    result = longest_subsequence(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>

int longestSubsequence(std::vector<int>& nums) {
    int sum = 0, xorResult = 0;

    for (int x : nums) {
        sum += x;
        xorResult ^= x;
    }

    if (sum == 0) {
        return0;  // nums 全为 0，无解
    }

    int result = nums.size();
    if (xorResult == 0) {
        result--;  // 去掉 nums 的一个非零元素，就可以使 xor 不为 0
    }

    return result;
}

int main() {
    std::vector<int> nums = {2, 3, 4};
    int result = longestSubsequence(nums);
    std::cout << result << std::endl;

    return0;
}