如何找到异或为0的最长连续子数组

Question

例如，给定 {1,1,2,2}：这些子数组的异或都为 0：{1,1}、{2,2}、{1,1,2,2}。最长的长度是4.

找到最长子数组的长度和return这个子数组的开始和结束索引。

Answer 1

计算数组的运行异或，从0个元素到所有元素。以你的例子：

initial 
segment         XOR
[]              0
[1]             1
[1, 1]          0
[1, 1, 2]       2
[1, 1, 2, 2]    0

如果两个运行异或值相同，则这两个值之间的子数组将异或为 0。

创建两个映射，存储第一个和最后一个异或值。运行通过它们，找出差异最大的一对。

在Python中：

def continuous_xor(xs):
    xor = 0
    first_seen = {0: 0}
    last_seen = {0: 0}
    for i, x in enumerate(xs):
        xor = xor ^ x
        if xor not in first_seen:
            first_seen[xor] = i+1
        last_seen[xor] = i+1
    return max((last_seen[i]-first_seen[i], first_seen[i], last_seen[i]) for i in last_seen)

print continuous_xor([1, 1, 2, 2])
print continuous_xor([5, 1, 4, 3, 2, 4, 6])

子数组的索引是Python式，起始索引是包含的，结束索引是不包含的。

这在 O(n) 时间内运行，其中 n 是输入数组的大小。

如何找到异或为0的最长连续子数组

How to find the longest contiuous subarray whose XOR is 0

algorithm

dynamic-programming

sub-array

subsequence