这是O(n)
基于问题描述下 CiaPan 评论的解决方案:
如果索引 I 到 J-1 处的项目的异或等于从 J 到 K 的异或,则从 I 到 K 的异或等于零。对于任何这样的子数组 [I .. K],I+1 和 K-1 之间的每个 J 都构成满足要求的三元组。从 I 到 K 的 xor 等于 (xor from 0 to K) xor (xor from 0 to I-1)。所以我想你可能会找到序列中所有可能的初始部分的异或,并寻找它们的相等对。
该函数f
是主要方法。brute_force
用于验证。
Python 2.7 代码:
import random
def brute_force(A):
res = 0
for i in xrange(len(A) - 1):
left = A[i]
for j in xrange(i + 1, len(A)):
if j > i + 1:
left ^= A[j - 1]
right = A[j]
for k in xrange(j, len(A)):
if k > j:
right ^= A[k]
if left == right:
res += 1
return res
def f(A):
ps = [A[0]] + [0] * (len(A) - 1)
for i in xrange(1, len(A)):
ps[i] = ps[i- 1] ^ A[i]
res = 0
seen = {0: (-1, 1, 0)}
for i in xrange(len(A)):
if ps[i] in seen:
prev_i, i_count, count = seen[ps[i]]
new_count = count + i_count * (i - prev_i) - 1
res += new_count
seen[ps[i]] = (i, i_count + 1, new_count)
else:
seen[ps[i]] = (i, 1, 0)
return res
for i in xrange(100):
A = [random.randint(1, 10) for x in xrange(200)]
f_A, brute_force_A = f(A), brute_force(A)
assert f_A == brute_force_A
print "Done"