全体异或判零 —— 最长非零异或子序列

日期: 2026-08-15

难度: Medium

标签: 位运算、子序列、数学

题目链接：[3702. 按位异或非零的最长子序列]

题目描述

给定数组 nums，返回按位异或结果非零的最长子序列的长度。不存在则返回 0。

示例 1：[1,2,3] → 2（2 ^ 3 = 1）
示例 2：[2,3,4] → 3（2 ^ 3 ^ 4 = 5）

第一次思路

第一反应是贪心：从头到尾累加异或，只要当前异或非零就更新答案长度。

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        int temp = nums[0];
        for (int i = 1; i < n; ++i) {
            temp ^= nums[i];
            if (temp != 0) res = i + 1;
        }
        return res == 0 ? 1 : res;
    }
};

反思：贪心的策略默认数组是”连续”的，但题目要的是子序列。反例 [7, 0, 7, 0, 0]：贪心扫描到 7 ^ 0 ^ 7 = 0 就断了，以为只能取前两个；实际上删掉中间的元素（比如取两个 7 和两个 0 之外的组合）能凑出更长的非零异或子序列。连续性假设在这个问题上不成立。

最终方案

正面想”选哪些元素、怎么组合”太复杂，反过来想：如果全部元素都选，会怎样？

记全体异或为 total，分三种情况：

total != 0：全部选上就是答案，长度为 n。
数组全为 0：任何子序列异或都是 0，答案 0。
其余情况（total == 0 且存在非零元素）：答案 n - 1。

这里主要来看看第 3 种情况的证明过程：首先随便取一个非零元素 a，剩余所有元素异或为 b。因为 total == 0，所以 a ^ b = 0，即 a == b。删掉 a 后剩余元素异或等于把 a 换成 0 再异或，即 0 ^ b = b != 0。非零，成立！

关键点：异或里”删掉一个元素”等价于”再异或一次这个元素”（a ^ a = 0），所以删元操作是免费的、确定有效的——只要全体异或为 0 且不全为 0，删掉任意一个非零元素就必然得到非零结果。

完整代码

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int total = 0;
        for (int v : nums) total ^= v;
        if (total != 0) return nums.size();       // 全选即可
        if (*max_element(nums.begin(), nums.end()) == 0) return 0;  // 全为 0
        return nums.size() - 1;                   // 删掉任意一个非零元素
    }
};

相比贪心版的改动：不再维护”连续”的临时异或，而是先算全体异或，再按三种情况直接给结论——问题从”枚举组合”转换为了了”分类讨论”。

复杂度分析

复杂度	分析
时间复杂度	O(n) — 一次遍历求异或 + 一次找最大值
空间复杂度	O(1) — 只用了常数个变量

心得总结

子序列题先排除连续性贪心——能删元素意味着”局部扫描”的结论都不成立，得从全局性质下手。
数学性质上整道题只有两个恒等式：x ^ x = 0、x ^ 0 = x。异或的”自反性”让删元变成零成本操作，这是它和加减法最不一样的地方。
任何题目我们都是从特殊到一般的情况去考虑的，先想清楚最特殊的情况下的解法是什么，然后在一步步扩展到一般的情况。