関小君刷题记

题目大意：

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

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1442

解题思路分析：

这道题目实际上可以这样理解，给定一个数组，然后让你找到2个子数组，两个子数组的范围可以表示为：

[i, j-1] // 数组1的范围
[j, k] // 数组2的范围
// 0 <= i < j <= k < arr.length

最后求出这两个子数组中所有元素亦或值相同的可能。

由于题目给出的数据规模并不大，因此暴力解法是可行的。我们使用三层循环来分别遍历i，j，k这三个变量。其中i的取值范围是下标0到数组最后一位。j的取值范围是i加一到数组最后一位，k的取值范围为j到数组最后一位。循环中我们分别查看两个子数组的亦或值是否相同即可。另外，本题为了提高效率，我们不用每次循环都去求一遍两个数组的亦或值。这里我们可以采用前缀数组来简化计算步骤。之前的文章我们多次讲过前缀和数组，而前缀亦或数组与前缀和数组原理形同，我们也曾提到过。（参考LEETCODE 1310. XOR Queries of a Subarray 解题思路分析）

比如我们定义前缀数组为pre[]，其中pre[0]等于arr[0]，pre[i]=pre[i-1]^arr[i]。因此对于任意一个区间的[x,y]的亦或值我们可以通过前缀数组来取得，即：

int xorXY = pre[x-1] ^ pre[y]; // 当x大于0时，区间x到y之间数值的亦或值
int xorXY = pre[y] // 当x等于0时

实现代码：

public int countTriplets(int[] arr) {
    // 前缀亦或数组
    int[] pre = new int[arr.length];
    pre[0]=arr[0];
    for(int i=1;i<arr.length;i++){
        pre[i] = (arr[i]^pre[i-1]);
    }
    int res=0; // 返回结果
    // 循环每一种情况
    for(int i=0;i<arr.length;i++){
        for(int j=i+1;j<arr.length;j++){
            for(int k=j;k<arr.length;k++){
                int x1; // 第一个数组的亦或值
                if(i==0){
                    x1=pre[j-1];
                }else{
                    x1=(pre[i-1]^pre[j-1]);
                }
                // 第一个数组与第二个数组亦或值相同时，结果加一
                if(x1==(pre[j-1]^pre[k])){
                    res++;
                }
            }
        }
    }
    return res;
}

本题解法执行时间为48ms。

Runtime: 48 ms, faster than 25.00% of Java online submissions for Count Triplets That Can Form Two Arrays of Equal XOR.

Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Count Triplets That Can Form Two Arrays of Equal XOR.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1442-count-triplets-that-can-form-two-arrays-of-equal-xor-解题思路分析/