2020-09-08LeetCode3 minutes read (About 493 words) 0 visits

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

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

给你一个整数数组 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：

1
2
3

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题还是和前缀异或有关，与异或相关的题目都逃不出异或那几个最基本的性质，本题说白了就是数组中两段异或值相等即让结果加一。具体来说，用两个变量确定区间的起始和结尾，根据异或性质有前缀异或：

$\begin{aligned} S_i \ xor \ S_j &= (arr_0 \ xor \ arr_1 \dots arr_{i-1}) \ xor \ (arr_0 \ xor \ arr_1 \dots arr_{i - 1} \ xor \ arr_i \ xor \ arr_{j-1}) \\ &= arr_i \ xor \dots \ xor arr_{j-1} \end{aligned}$

对于本题来说，$a=b$有$S_{i} xor S_{temp} = S_{temp} xor S_{j+1}$，即$S_i = S{j+1}$，对于该式可以看到和区间中间点选取无关，故在$[i+1, j]$之间任意 temp 都是满足要求的。

具体代码如下：

class Solution {
    public int countTriplets(int[] arr) {
        int[] temp = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; i++) {
            temp[i] = temp[i - 1] ^ arr[i - 1];
        }

        int result = 0;
        for (int i = 1; i <= arr.length; i++) {
            for (int j = i + 1; j <= arr.length; j++) {
                if (temp[i - 1] == temp[j]) {
                    result += (j - i);
                }
            }
        }
        return result;
    }
}