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

标签: 位运算数组哈希表数学前缀和

难度: Medium

给你一个整数数组 arr 。

现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。

a 和 b 定义如下：

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

注意：^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例 1：

输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例 2：

输入：arr = [1,1,1,1,1]
输出：10

示例 3：

输入：arr = [2,3]
输出：0

示例 4：

输入：arr = [1,3,5,7,9]
输出：3

示例 5：

输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8

提示：

1 <= arr.length <= 300
1 <= arr[i] <= 10^8

Submission

运行时间: 28 ms

内存: 16.0 MB

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] ^ arr[i - 1]
        ans = 0
        preL = dict()
        preL[prefix[1]] = [0]
        preL[0] = [-1]
        for i in range(1, n):
            if prefix[i + 1] in preL:
                for j in preL[prefix[i + 1]]:
                    ans += (i - j - 1)
                preL[prefix[i + 1]].append(i)
            else:
                preL[prefix[i + 1]] = [i]
        return ans

Explain

这道题目可以通过使用异或前缀和数组来解决，利用异或运算的性质，即 a^b = 0 当且仅当 a = b。构建一个前缀和数组 prefix，其中 prefix[i] 是从 arr[0] 到 arr[i-1] 的异或和。若要满足 a == b，则需要 prefix[j] ^ prefix[i] == prefix[k+1] ^ prefix[j]，简化后可得 prefix[i] == prefix[k+1]。遍历每一个 k，查看 prefix[k+1] 是否在之前出现过，若出现，则可以计算出满足条件的 (i, j, k) 数目。通过字典 preL 来记录每个前缀和出现的所有位置，然后针对每一个位置，根据之前存储的位置索引计算三元组数目。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0] * (n + 1)  # 创建前缀和数组
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] ^ arr[i - 1]  # 计算前缀和
        ans = 0  # 存储满足条件的三元组数
        preL = dict()  # 存储前缀和及其出现的所有位置
        preL[prefix[1]] = [0]  # 初始化字典
        preL[0] = [-1]  # 用于处理从起点开始的情况
        for i in range(1, n):
            if prefix[i + 1] in preL:
                for j in preL[prefix[i + 1]]:
                    ans += (i - j - 1)  # 计算从 j+1 到 i 的满足条件的数目
                preL[prefix[i + 1]].append(i)  # 更新当前前缀和的位置
            else:
                preL[prefix[i + 1]] = [i]  # 如果未出现过，记录位置
        return ans  # 返回结果

Explore

在构造前缀和数组时，选择`n + 1`的长度是为了包含从数组开头到任意位置的异或和，并且方便地计算从数组的起点开始的子数组异或和。具体来说，`prefix[0]`被初始化为0，这代表了一个空的前缀，即没有任何元素的异或结果。这样设置可以使得当我们考虑从数组的第一个元素到第i个元素的异或和时，可以直接使用`prefix[i]`表示，而不需要额外的条件判断。此外，这样的设置还便于处理边界条件，使得代码更加简洁和易于理解。

这个简化过程基于异或运算的性质。给定`prefix[j] ^ prefix[i] == prefix[k+1] ^ prefix[j]`，使用异或运算的消除性质，我们可以两边同时异或`prefix[j]`。根据异或运算的性质，任何数与自身异或的结果为0，即`a ^ a = 0`，并且异或运算满足交换律和结合律。因此，将`prefix[j]`异或到等式两边，我们得到`prefix[j] ^ prefix[j] ^ prefix[i] = prefix[k+1] ^ prefix[j] ^ prefix[j]`。简化后，等式两边的`prefix[j] ^ prefix[j]`都变为0，因此等式变为`0 ^ prefix[i] = 0 ^ prefix[k+1]`，即`prefix[i] = prefix[k+1]`。这是利用异或运算的特性进行的等式变换。

在字典`preL`的初始化中，将`0`与`[-1]`关联起来是为了处理从数组的第一个元素开始的子数组的情况。由于`prefix[0]`被设置为0（表示一个空前缀），我们需要记录这个值出现的位置，以便在后续计算中使用。`-1`作为索引表示的是一个虚拟的起始位置，它使得当我们考虑从数组的第一个元素开始的子数组时，能够正确地计算出子数组的开始位置。例如，如果`prefix[1]`也是0，那么根据异或运算的性质，从第一个元素到当前元素的整个子数组的异或和为0，我们需要这样的初始化来正确地处理这类情况。相似地，将`prefix[1]`与`[0]`关联起来是因为`prefix[1]`实际上表示从数组开始到第一个元素的异或和，记录这个位置是为了在后续遍历中能够追踪到每个前缀和首次出现的位置。