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

2021-05-18

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

难度中等65

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

异或前缀

计算一个区间的所有数字的异或结果的时候，可以通过前缀来进行，查询区间[x,y]的异或结果Q[x,y]时有以下结论：

当x = 0时：
- Q[x,y] = xors[y]
当x > 0时
- Q[x,y] = xors[x-1] ^ xors[x-1] ^ Q[x,y] =xors[x-1]^xors[y]

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

        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                for(int k = j; k < n; k++){
                    if(i>0 && (xors[j] ^ xors[i-1]) == (xors[k] ^ xors[j])){
                        res++;
                    }else if(i==0 && xors[j] == (xors[k] ^ xors[j])){
                        res++;
                    }
                }
            }
        }
        return res;
    }
}

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true