algorithm - 查找 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;
}