LeetCode 1442：异或相等三元组的高效解法

1. 题目解析与核心概念这道题目来自LeetCode第1442题题目描述如下给定一个整数数组arr我们需要统计能够形成两个异或相等数组的三元组(i, j, k)的数目其中0 ≤ i j ≤ k arr.length。首先我们需要明确几个关键概念三元组(i, j, k)表示数组中的三个索引位置满足i j ≤ k的关系异或(XOR)运算按位异或操作相同为0不同为1异或相等数组题目中定义a arr[i] ^ arr[i1] ^ ... ^ arr[j-1]b arr[j] ^ arr[j1] ^ ... ^ arr[k]要求a b理解这个题目需要掌握异或运算的一个重要性质如果a ^ b 0那么a b。这个性质是解决本题的关键。2. 异或运算的性质与应用异或运算有几个非常重要的性质在解决这个问题时需要充分理解交换律a ^ b b ^ a结合律a ^ (b ^ c) (a ^ b) ^ c自反性a ^ a 0恒等性a ^ 0 a基于这些性质我们可以推导出一个重要的结论如果a ^ b 0那么a b。这个结论直接对应题目中要求a b的条件。另一个关键点是异或前缀和的概念。我们可以预先计算一个前缀异或数组xor其中xor[i]表示arr[0] ^ arr[1] ^ ... ^ arr[i-1]。这样任意子数组arr[i..j]的异或和可以表示为xor[j1] ^ xor[i]。3. 暴力解法与分析最直观的解法是使用三重循环枚举所有可能的三元组(i, j, k)然后计算a和b的值进行比较def countTriplets(arr): n len(arr) count 0 for i in range(n): for j in range(i1, n): a 0 for x in range(i, j): a ^ arr[x] for k in range(j, n): b 0 for y in range(j, k1): b ^ arr[y] if a b: count 1 return count这个解法的时间复杂度是O(n^4)因为有三重循环且在最内层还有计算a和b的循环。对于较大的n来说这种解法显然效率太低无法通过LeetCode的测试用例。4. 优化思路与数学推导我们需要寻找更高效的解法。根据异或的性质我们知道如果a b那么a ^ b 0。而根据前缀异或的定义a ^ b (arr[i] ^ ... ^ arr[j-1]) ^ (arr[j] ^ ... ^ arr[k]) arr[i] ^ ... ^ arr[k] xor[k1] ^ xor[i]因此a b等价于xor[k1] ^ xor[i] 0即xor[k1] xor[i]。这意味着对于任意i和k如果xor[k1] xor[i]那么对于i和k之间的任意ji j ≤ k三元组(i, j, k)都满足题目条件。因此这样的(i, k)对对应的有效j的数目是k - i。基于这个观察我们可以将问题转化为统计所有满足xor[k1] xor[i]的(i, k)对然后对每个这样的对累加k - i到结果中。5. 优化后的算法实现基于上述推导我们可以实现一个O(n^2)的解法def countTriplets(arr): n len(arr) xor [0] * (n 1) for i in range(n): xor[i1] xor[i] ^ arr[i] count 0 for i in range(n): for k in range(i1, n): if xor[k1] xor[i]: count (k - i) return count这个解法首先计算前缀异或数组xor然后双重循环遍历所有可能的i和ki k检查xor[k1]是否等于xor[i]如果相等则累加k - i到结果中。6. 进一步优化到O(n)我们可以进一步优化这个解法到O(n)时间复杂度。观察到对于每个k我们需要统计前面所有i满足xor[i] xor[k1]的(k - i)之和。我们可以使用一个哈希表来记录每个异或值出现的次数和位置索引的和。具体来说维护一个字典记录每个异或值出现的次数count和所有出现该异或值的索引i的和total对于每个位置k计算当前前缀异或xor[k1]如果xor[k1]在字典中则结果增加count * k - total更新字典将当前xor[i]即xor[k]的信息存入字典实现代码如下def countTriplets(arr): n len(arr) xor 0 count_map {0: (1, 0)} # (count, total_index_sum) res 0 for k in range(n): xor ^ arr[k] if xor in count_map: cnt, total count_map[xor] res cnt * k - total # 更新xor ^ arr[k]的信息即xor[i]的信息 if xor in count_map: cnt, total count_map[xor] count_map[xor] (cnt 1, total k 1) else: count_map[xor] (1, k 1) return res这个解法只需要一次遍历数组时间复杂度降为O(n)空间复杂度为O(n)用于存储哈希表。7. 代码实现细节与测试让我们详细分析一下最优解法的实现细节初始化xor为0表示空数组的异或和初始化count_map记录异或值为0出现了1次位置索引和为0遍历数组计算当前的前缀异或xor ^ arr[k]如果当前xor在count_map中说明存在i使得xor[i] xor[k1]可以形成有效三元组计算结果res cnt * k - totalcnt是相同异或值出现的次数total是这些i的和更新count_map将当前xor实际上是xor[i]的值的信息存入测试用例示例print(countTriplets([2,3,1,6,7])) # 输出4 print(countTriplets([1,1,1,1,1])) # 输出10 print(countTriplets([2,3])) # 输出0 print(countTriplets([1,3,5,7,9])) # 输出38. 复杂度分析与比较让我们比较一下三种解法的复杂度暴力解法O(n^4)时间O(1)空间前缀异或优化O(n^2)时间O(n)空间哈希表优化O(n)时间O(n)空间在实际应用中当n较大时如n10^5只有O(n)的解法能够在合理时间内完成。对于LeetCode的测试用例O(n^2)的解法通常也能通过但O(n)是最优解。空间复杂度方面O(n)的解法需要额外的哈希表空间但在现代计算机上这对于中等规模的数组来说不是问题。9. 常见错误与调试技巧在实现这个算法时容易犯的几个错误索引处理错误特别是在计算前缀异或数组时xor[i]表示arr[0..i-1]的异或和容易混淆i的起始位置哈希表更新时机错误应该在计算完结果后再更新哈希表否则会包含当前元素自身三元组条件理解错误必须满足i j ≤ k不能有i j或j k的情况调试技巧对于小数组手动计算几个例子的结果验证代码正确性打印中间变量如前缀异或数组检查计算是否正确使用LeetCode的测试用例和自定义边界条件测试10. 扩展思考与类似题目这个问题可以扩展到更一般的情况比如统计满足其他位运算条件的子数组如AND、OR等统计满足多个条件的复合三元组在树或其他数据结构上应用类似的异或性质类似题目推荐LeetCode 1310. 子数组异或查询LeetCode 1720. 解码异或后的数组LeetCode 1734. 解码异或后的排列这些题目都利用了异或运算的性质来优化解法掌握这些技巧可以大大提高解决位运算相关问题的能力。