Leetcode 1442. Count Triplets That Can Form Two Arrays of Equal XOR (python)

题目

解法：prefix XOR

这道题目解法基于几个结论：

• We are searching for sub-array of length ≥ 2 and we need to split it to 2 non-empty arrays so that the xor of the first array is equal to the xor of the second array. This is equivalent to searching for sub-array with xor = 0. Because XOR for two same number is 0.
• if xor for an array is 0, then pick any position to split the arry to two subarrays, the xor for the subarrays should be the same
• prefix xor helps to reduce the time complexity to O(n^2)

class Solution:def countTriplets(self, arr: List[int]) -> int:n = len(arr)if n<2:return 0prefix_xor = [0]tmp = 0for num in arr:tmp ^= numprefix_xor.append(tmp)#print(prefix_xor)ans = 0for i in range(n+1):for j in range(i+2,n+1):if prefix_xor[j]^prefix_xor[i] == 0:#print(j,i)ans += j-i-1return ans