找到特殊子数组的数量，使得第一个和最后一个元素的按位异或等于子数组中所有其他元素的异或

Question

给定一个整数数组，找到长度至少为 3 的子数组的数量，其中子数组中第一个和最后一个元素的按位异或等于子数组中其余元素。你能想出比 O(N^2) 更好的解决方案吗

我使用 prefix_array 想出了 O(n^2) 解决方案。我想知道是否有比这更好的解决方案，因为我的解决方案无法通过最后几个测试用例。

Answer 1

如果两个边缘元素的按位异或等于内部元素的异或，则整个子数组的异或为零。

因此，您可以计算前缀异或和，将它们放入字典中，然后“动态”检查字典中是否已存在正确的对和。

看类似的问题（通常是求和，也不是异或），也包含大小>=3的技巧