给定一个数组；我需要子数组；其元素的异或值等于某个给定值

Question

假设我有： arr={4，2，2，6，4} 和 m=6（我需要检查哪些子数组的异或得到6）

因此子数组将是： {4，2}，{4，2，2，6，4}，{2，2，6}和{6}（总计=4）

我需要的是：每个子数组（或它们各自的长度）的开始和结束索引—在O（n）时间内。你知道吗

我需要一个O（n）方法，所以我尝试了在一个网站上找到的以下代码。问题是它给出了这样的子数组的“数目”。你知道吗

def subarrayXor(arr, n, m):   
    ans = 0 
    # Create a prefix xor-sum array such that 
    # xorArr[i] has value equal to XOR 
    # of all elements in arr[0 ..... i] 
    xorArr =[0 for _ in range(n)] 

    # Create map that stores number of prefix array 
    # elements corresponding to a XOR value 
    mp = dict() 

    # Initialize first element  
    # of prefix array 
    xorArr[0] = arr[0] 

    # Computing the prefix array. 
    for i in range(1, n): 
        xorArr[i] = xorArr[i - 1] ^ arr[i] 

    # Calculate the answer 
    for i in range(n): 

        # Find XOR of current prefix with m. 
        tmp = m ^ xorArr[i] 

        # If above XOR exists in map, then there 
        # is another previous prefix with same 
        # XOR, i.e., there is a subarray ending 
        # at i with XOR equal to m. 
        if tmp in mp.keys(): 
            ans = ans + (mp[tmp]) 

        # If this subarray has XOR  
        # equal to m itself. 
        if (xorArr[i] == m): 
            ans += 1

        # Add the XOR of this subarray to the map 
        mp[xorArr[i]] = mp.get(xorArr[i], 0) + 1

    return ans 

Answer 1

我有一个O（n**2）的解。如果这可以以某种方式进行修改以减少到O（n）的时间，则将是值得赞赏的。你知道吗

n = int(input())
a = [int(i) for i in input().split()]
suff = list(a) #suffix xor
for i in range(1,n):
     suff[i] = suff[i-1]^a[i]
    #print(suff)
m = int(input())
out = list()
for i in range(0,n-1):
    for j in range(i+1,n):
        if i != 0:
            B = suff[i-1]^suff[j]
            if B == m:
                out.append([i,j])
        else:
            if suff[j] == m:
                out.append([i,j])

print(out)