查找 xor 为 0 的子数组

Question

我遇到了一个问题，即找到一个 xor 为 0 的子数组。我在某处读到这可以使用 TRIE 数据结构来完成，但我想要数组的开始和结束索引。

例如，考虑一个数组

a = [3, 6, 13, 8 15]

从 0 到 3 的子数组即 [3, 6, 13, 8] 的异或等于 0。 (3 xor 6 xor 13 xor 8 = 0) 我正在寻找一种可以找到这些索引的算法（在本例中为 [0, 3]）。

详细的回答会很有帮助。

更新我尝试了蛮力方法查找所有 [i, j] 对的异或检查。这给了 TLE 因为没有。数组中的元素最多可以达到 10^5

我尝试了提到的解决方案 here 但这没有给出索引。

我正在寻找复杂度为 O(nLogn) 或可能为 O(n) 的算法。

Answer 1

此解决方案也具有 O(n) 的复杂性。利用 unordered_map.

vector<int> a = {3,6,13,8,15};
unordered_map<int, int> hashMap;
int number_of_elements = a.size();
hashMap[0] = -1;
int xor_sum = 0;
for(int i = 0; i < number_of_elements; i++) {
    xor_sum ^= a[i];
    if(hashMap.find(xorSum) != hashMap.end()) {
        cout << hashMap[xorSum] + 1 << " " << i << endl;
        break;
    }
    hashMap[xor_sum] = i;
}

查找 xor 为 0 的子数组

Finding subarray whose xor is 0

algorithm

bit-manipulation

xor

trie

bitwise-xor