求异或为0的子阵

Question

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

例如，考虑一个数组

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

我正在寻找一个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;
}