JZX轻语：简

LeetCode 1442 - 形成两个异或相等数组的三元组数目

发表于2024年08月22日

不难得知，对于满足条件的三元组(i,j,k)，由于arr[i..j-1]的异或结果a等于arr[j..k]的异或结果a，那么a和b的异或结果为0，换句话说，子数组arr[i..k]所有的元素异或结果为0。反过来思考，如果某个长度为l的子数组中，所有元素异或的结果为0，那么该子数组中可以构造l - 1个满足条件的三元组。因此，题目转化为寻找所有元素异或结果为0的子数组，并计算其长度l，然后累加l - 1的和。

怎么寻找这些子数组呢？我们可以使用一个数组prev_xor，其中prev_xor[i]表示第i个元素到当前元素的异或结果。那么可从左到右遍历数组arr，更新prev_xor，如果更新后某个prev_xor[i]的结果为0，那么从i到j的子数组满足条件，此时可以构造j - i个三元组。

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        prev_xor = [0] * len(arr)
        ans = 0
        for i, num in enumerate(arr):
            for j in range(i - 1, -1, -1):
                prev_xor[j] ^= num
                if prev_xor[j] == 0:
                    ans += (i - j)
            prev_xor[i] = num
        return ans