求满足特定异或条件的长度≥3的子数组个数，寻求优于O(N²)的解法

问题转化 #

首先利用异或运算的特性，将题目条件等价转换：
题目要求子数组nums[i...j]（长度≥3）满足nums[i] XOR nums[j] = XOR(nums[i+1]...nums[j-1])。
设整个子数组的异或和为S = nums[i] XOR nums[i+1] ... XOR nums[j]，代入条件可得：
nums[i] XOR nums[j] = S XOR nums[i] XOR nums[j]
两边同时异或nums[i] XOR nums[j]，可推导出S = 0。

因此问题简化为：统计数组中长度≥3且异或和为0的子数组个数。

O(N)时间复杂度解法 #

核心思路 #

利用前缀异或数组+哈希表实现线性统计：

1. 前缀异或数组定义：
   设prefix[0] = 0，prefix[k] = nums[0] XOR nums[1] ... XOR nums[k-1]（前k个元素的异或和）。
   子数组nums[i...j]的异或和等于prefix[j+1] XOR prefix[i]，当且仅当prefix[j+1] = prefix[i]时，该子数组异或和为0。

2. 哈希表统计规则：
   我们需要筛选出满足j+1 - i ≥3（子数组长度≥3）的(i,j)对，即i ≤ (j+1)-3。
   具体步骤：

   • 初始化哈希表count，记录前缀异或值的出现次数，初始时count[prefix[0]] = 1（对应i=0的情况）。
   • 初始化结果变量res = 0。
   • 遍历前缀异或数组的索引k（从1到n）：
     • 当k ≥3时，将prefix[k-2]加入哈希表（后续遍历到更大的k'时，i=k-2对应的子数组长度会≥3，符合统计条件）。
     • 若prefix[k]存在于哈希表中，将对应次数累加到res（这些次数对应的i均满足i ≤k-3，子数组长度≥3）。

代码实现（Python） #

from collections import defaultdict

def count_valid_subarrays(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] ^ nums[i-1]
    
    count = defaultdict(int)
    count[prefix[0]] = 1
    res = 0
    
    for k in range(1, n + 1):
        if k >= 3:
            count[prefix[k-2]] += 1
        res += count.get(prefix[k], 0)
    
    return res

复杂度分析 #

• 时间复杂度：O(N)，仅需两次线性遍历（计算前缀异或、统计结果），哈希表操作均为O(1)。
• 空间复杂度：O(N)，最坏情况下前缀异或值无重复，哈希表需存储N+1个元素。

内容的提问来源于stack exchange，提问作者Jianing Li