查找xor为0的子数组 [英] Finding subarray whose xor is 0

问题描述

我陷入一个难题，即找到一个xor为0的子数组。
我读到某个地方，可以使用TRIE数据结构完成此操作，但是我想要数组的开始和结束索引。

例如，考虑一个数组

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

子数组从0到3，即[3，6，13，8]的xor等于0。
（3 xor 6 xor 13 xor 8 = 0）
我正在寻找一种算法，无法找到那些索引（在这种情况下为[0，3]）。

详细的答案将非常有帮助。 p>

更新
我尝试了蛮力方法来检查所有[i，j]对的xor值。由于没有，所以给了TLE。数组中元素的最大数量为10 ^ 5

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

我正在寻找一种算法

解决方案

此解决方案采用 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<< <<我<<恩德尔
休息时间； 
} 
 hashMap [xor_sum] = i; 
} 
  

I'm stuck at one problem i.e. to find a subarray whose xor is 0. I read somewhere that this can be done using TRIE data structure but I want the starting and ending indices of the array.

For example, consider an array

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

The subarray from 0 to 3 i.e. [3, 6, 13, 8] has xor equal to 0. (3 xor 6 xor 13 xor 8 = 0) I'm in search for an algorithm than can find those indices ([0, 3] in this case).

Detailed answer would be very helpful.

Update I tried the brute Force approach find checking xor for all pairs of [i, j]. This gives TLE since the no. of elements in the array could be upto 10^5

The I tried a solution mentioned here but this doesn't give indices.

I'm looking for an algorithm with O(nLogn) or possibly O(n) complexity.

解决方案

This solution take O(n) complexity also. Take the benefit of 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的子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！