位运算题目：形成两个异或相等数组的三元组数目

题目

标题和出处

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

出处：1442. 形成两个异或相等数组的三元组数目

难度

5 级

题目描述

要求

给定一个整数数组 $\text{arr}$。

现需要从数组中取三个下标 $\text{i}$、$\text{j}$ 和 $\text{k}$，其中 $\text{0}\le \text{i}<\text{j}\le \text{k}<\text{arr.length}$。

定义 $\text{a}$ 和 $\text{b}$ 如下：

• $\text{a}=\text{arr[i]}\oplus \text{arr[i + 1]}\oplus \dots \oplus \text{arr[j - 1]}$
• $\text{b}=\text{arr[j]}\oplus \text{arr[j + 1]}\oplus \dots \oplus \text{arr[k]}$

$\oplus$ 表示按位异或操作。

返回使 $\text{a}=\text{b}$ 成立的三元组 $\text{(i, j, k)}$ 的数目。

示例

示例 1：

输入：$\text{arr = [2,3,1,6,7]}$
输出：$\text{4}$
解释：满足题意的三元组分别是 $\text{(0,1,2)}$、$\text{(0,2,2)}$、$\text{(2,3,4)}$ 和 $\text{(2,4,4)}$。

示例 2：

输入：$\text{arr = [1,1,1,1,1]}$
输出：$\text{10}$

数据范围

• $\text{1}\le \text{arr.length}\le \text{300}$
• $\text{1}\le \text{arr[i]}\le {\text{10}}^{\text{8}}$

解法一

思路和算法

对于选定的三个下标 $i$、$j$ 和 $k$，其中 $i<j\le k$，$a$ 等于数组 $\text{arr}$ 的下标范围 $[i,j-1]$ 中的所有元素的按位异或运算结果，$b$ 等于数组 $\text{arr}$ 的下标范围 $[j,k]$ 中的所有元素的按位异或运算结果，因此 $a\oplus b$ 等于数组 $\text{arr}$ 的下标范围 $[i,k]$ 中的所有元素的按位异或运算结果。

根据按位异或运算的性质，$a=b$ 等价于 $a\oplus b=0$。如果数组 $\text{arr}$ 的下标范围 $[i,k]$ 中的所有元素的按位异或运算结果等于 $0$，则对于任意满足 $i<j\le k$ 的下标 $j$ 都有 $a\oplus b=0$，等价于 $a=b$，因此在确定 $i$ 和 $k$ 的情况下，$j$ 可以取 $i+1$ 到 $k$ 的任意下标，有 $k-i$ 种取值。

为了计算符合要求的三元组的数目，需要遍历数组 $\text{arr}$ 的所有子数组，对于每个子数组计算子数组中的所有元素的按位异或运算结果。如果一个下标范围是 $[i,k]$ 的子数组中的所有元素的按位异或运算结果等于 $0$，则该子数组中符合要求的三元组的数目是 $k-i$，将该数目加到答案中。遍历全部子数组之后，即可得到符合要求的三元组的数目。

代码

class Solution {public int countTriplets(int[] arr) {int count = 0;int length = arr.length;for (int i = 0; i < length; i++) {for (int k = i + 1; k < length; k++) {int xor = 0;for (int j = i; j <= k; j++) {xor ^= arr[j];}if (xor == 0) {count += k - i;}}}return count;}
}

复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是数组 $\text{arr}$ 的长度。数组 $\text{arr}$ 的子数组个数是 $O(n^2)$，对于每个子数组需要 $O(n)$ 的时间计算子数组中的所有元素的按位异或运算结果，因此时间复杂度是 $O(n^3)$。

• 空间复杂度：$O(1)$。

解法二

思路和算法

解法一当中对于每个子数组计算所有元素的按位异或运算结果需要 $O(n)$ 的时间，可以将计算按位异或运算结果的时间降低到 $O(1)$。

当子数组的开始下标 $i$ 确定时，每个大于等于 $i$ 的下标 $k$ 都可以作为子数组的结束下标。假设下标范围 $[i,k-1]$ 对应的按位异或运算结果是 $\text{xor}$，则下标范围 $[i,k]$ 对应的按位异或运算结果等于 $\text{xor}\oplus \text{arr}[k]$。使用该方法，计算一个子数组中的所有元素的按位异或运算结果的时间是 $O(1)$。

代码

class Solution {public int countTriplets(int[] arr) {int count = 0;int length = arr.length;for (int i = 0; i < length; i++) {int xor = 0;for (int k = i; k < length; k++) {xor ^= arr[k];if (xor == 0) {count += k - i;}}}return count;}
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是数组 $\text{arr}$ 的长度。数组 $\text{arr}$ 的子数组个数是 $O(n^2)$，对于每个子数组计算子数组中的所有元素的按位异或运算结果的时间是 $O(1)$，因此时间复杂度是 $O(n^2)$。

• 空间复杂度：$O(1)$。