题目

3702. 按位异或非零的最长子序列

给你一个整数数组 nums，请你返回 nums 中最长的子序列的长度，使得该子序列所有元素的按位异或结果非零。如果不存在这样的子序列，返回 0。

子序列 是指从原数组中删除一些（或不删除）元素，且不改变剩余元素顺序得到的非空数组。

示例 1：

1
2
3
输入：nums = [1,2,3]
输出：2
解释：最长的按位异或非零子序列是 [2,3]（2 ^ 3 = 1）或 [1,2]（1 ^ 2 = 3），长度为 2。

示例 2：

1
2
3
输入：nums = [0,0,0]
输出：0
解释：任何子序列的异或结果都是 0，不存在非零异或的子序列。

示例 3：

1
2
3
输入：nums = [5]
输出：1
解释：整个数组的异或结果为 5，非零，长度为 1。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

思路

异或的核心性质

本题的关键在于利用异或运算的以下性质：

  1. 自反性：a ^ a = 0，任何数与自身异或得 0。
  2. 恒等性：a ^ 0 = a，任何数与 0 异或等于自身。
  3. 交换律与结合律：异或运算满足交换律和结合律。

基于这些性质，我们可以分三种情况讨论：

情况一：全局异或非零

设 totalXor = nums[0] ^ nums[1] ^ ... ^ nums[n-1]。如果 totalXor ≠ 0，那么整个数组本身就是合法的子序列，直接返回 n。

情况二：全局异或为零，且全部元素为零

如果所有元素都是 0，那么任何子序列的异或结果只能是 0，无法得到非零异或，返回 0。

情况三：全局异或为零，但存在非零元素

这是最需要思考的情况。设 totalXor = 0，且数组中至少有一个非零元素 x（x ≠ 0）。我们删除这一个元素，剩余 n-1 个元素的异或结果为：

1
剩余异或 = totalXor ^ x = 0 ^ x = x ≠ 0

因此，长度为 n-1 的子序列必然合法，返回 n-1。

为什么最长是 n-1 而不是更短？

因为我们的目标是最长子序列。当全局异或为 0 时，长度为 n 不合法，但 n-1 一定合法（只需去掉任意一个非零元素）。不存在比 n-1 更长的合法子序列。

算法流程

  1. 遍历数组，计算 totalXor（全局异或）和 zeroCount（零元素个数）。
  2. 若 totalXor ≠ 0，返回 n。
  3. 若 zeroCount == n，返回 0。
  4. 否则，返回 n - 1。

复杂度分析

  • 时间复杂度：O(n)，只需一次遍历。
  • 空间复杂度：O(1)，仅使用常数个变量。

出错分析：为什么滑动窗口不适用？

初看此题，可能会想到用滑动窗口维护一个「异或非零」的连续子数组，每次窗口异或变为 0 就收缩左边界。注释掉的代码便是这种思路：

1
2
3
4
5
6
7
8
9
10
xor = 0;
for (int left = 0, right = 0; right < nums.length; right++) {
    xor ^= nums[right];
    while (xor == 0 && left <= right) {
        xor ^= nums[left];
        left++;
    }
    ans = Math.max(ans, right - left + 1);
}
return ans;

然而，滑动窗口只能处理连续子数组，本题要求的是子序列（可以不连续）。这导致滑动窗口在两类场景下会出错。

反例一：全局异或非零，但中间异或归零

以 nums = [2, 2, 2] 为例，全局异或 2 ^ 2 ^ 2 = 2 ≠ 0，正确答案应为 3（整个数组）。

滑动窗口推演：

right 字符 xor while 收缩 窗口 ans
0 2 2 — [0,0] 1
1 2 2 ^ 2 = 0 移除 2，left=1 [1,1] 1
2 2 2 ^ 2 = 0 移除 2，left=2 [2,2] 1

最终返回 1，与正确答案 3 相去甚远。

根因：当 right=1 时前缀异或归零，窗口被迫收缩，丢弃了 nums[0]。但 nums[0] 和 nums[2] 组合（2 ^ 2 = 0）或三者组合（2 ^ 2 ^ 2 = 2）都是合法的——滑动窗口一旦丢弃左边元素，就再也找不回来了。

反例二：全局异或为零，但需要从中间删除元素

以 nums = [0, 1, 2, 3] 为例，全局异或 0 ^ 1 ^ 2 ^ 3 = 0，只需删除一个元素即可得到非零异或（如删除 0 得 1 ^ 2 ^ 3 = 0… 等等，删除 1 得 0 ^ 2 ^ 3 = 1 ≠ 0），正确答案为 3。

滑动窗口推演：

right 字符 xor while 收缩 窗口 ans
0 0 0 移除 0，left=1 空 0
1 1 1 — [1,1] 1
2 2 1 ^ 2 = 3 — [1,2] 2
3 3 3 ^ 3 = 0 移除 1，left=2；移除 2，left=3 [3,3] 2

最终返回 2，正确答案是 3。

根因：当 right=3 时窗口异或归零，滑动窗口从左边依次移除 1、2，最终只剩下 [3]。但实际上，正确的做法是跳过中间的某个元素（比如跳过 1，保留 [0, 2, 3]，异或 0 ^ 2 ^ 3 = 1 ≠ 0），而不是从左边逐个丢弃。滑动窗口无法表达「跳过中间元素」这个操作。

总结

对比维度 滑动窗口 正解（全局异或 + 分类讨论）
处理对象 连续子数组 子序列（可不连续）
丢弃方式 只能从左侧收缩 可从任意位置删除一个元素
全局异或 ≠ 0 可能因中间归零而丢失答案 直接返回 n
全局异或 = 0 可能因左侧收缩而丢失更长组合 利用 totalXor ^ x = x 得 n-1
时间复杂度 O(n) O(n)
正确性 ❌ ✅

核心教训：滑动窗口的「收缩左边界」只能丢掉前缀，无法跳过中间元素。当问题允许不连续的子序列时，滑动窗口就不再适用，需要从整体性质（如全局异或）入手。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestSubsequence(int[] nums) {
        int xor = 0, zeroCount = 0;
        for (int num : nums) {
            xor ^= num;
            if (num == 0) {
                zeroCount++;
            }
        }
        if (xor != 0) {
            return nums.length;
        }
        if (zeroCount == nums.length) {
            return 0;
        }
        return nums.length - 1;
    }
}

关键点

  1. 异或的自反性：a ^ a = 0，这意味着全局异或为 0 时，去掉任意一个元素 x 后，剩余异或恰好等于 x。只要 x ≠ 0，剩余异或就非零。
  2. 全零特判：当数组全是 0 时，无论去掉哪个元素，剩余异或始终为 0，因此必须单独处理。
  3. 子序列与子数组的区别：子序列不要求连续，因此可以从任意位置删除元素。本题中删除任意一个非零元素即可，不需要考虑顺序。
  4. 贪心本质：最长的合法子序列要么是全部（全局异或非零），要么是去掉一个（全局异或为零但非全零），不存在中间情况。

相关题目