1442. Count Triplets That Can Form Two Arrays of Equal XOR

https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

Given an array of integers arr.

We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let's define a and b as follows:

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]

• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (i, j and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

• 1 <= arr.length <= 300

• 1 <= arr[i] <= 10^8

对给定数组arr问三元组(i, j, k)满足xor(arr[i:j]) == xor(arr[j:k))的三元组个数。xor(arr[i:j]) == xor(arr[j:k))意味着xor(arr[i:j]) ^ xor(arr[j:k)) == xor(arr[i:j]) == 0，此时对k，遍历i，当prexor[i-1] ^ prexor[k] == 0时，意味着对i，k，能和中间的所有j组成满足条件的三元组，res += k - i，总时间复杂度O(N^2)；进一步因为prexor[i-1] ^ prexor[k] == 0时，prexor[i - 1] == prexor[k]，所以可以统计每次prexor[k]出现的频率和sum(出现的index)，也就是i-1的位置和，res += k - i for all i => res += freq(prexor[k]) * (k - 1) - (sum(i - 1) for all i that prexor[i - 1] == prexor[k])，初始时还有值0对应的位置-1和频率1，总时间复杂度O(N)。

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prexor, cur, res = {0: [1, -1]}, 0, 0
        for k, v in enumerate(arr):
            cur ^= v
            if cur not in prexor:
                prexor[cur] = [0, 0]
            f, t = prexor[cur]
            res += (k - 1) * f - t
            prexor[cur] = [f + 1, t + k]
        return res