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

力扣 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 <= arr.length <= 300
- 1 <= arr[i] <= 10^8

示例

示例 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

笔者理解

此题是一道位运算算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题中的a==b，其实就是a^b==0，此点需要注意，让我们来看看具体如何实现的吧。

实现

public int countTriplets(int[] arr) {
        // 前缀和加三重循环
        int n = arr.length;
        int result = 0;

        int[] values = new int [n];

        values[0] = arr[0];

        // 求出前n个数的异或值
        for (int i = 1; i < n; i++) {
            values[i] = values[i - 1] ^ arr[i];
        }

        // 遍历所有可能
        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 && values[k] == 0) {
                    //     result++;
                    // }

                    result = i + values[k] == 0? result + 1: result;

                    // 同下
                    // if (i > 0 && (values[j - 1] ^ values[i - 1]) == (values[k] ^ values[j - 1])) {
                    //     result++;
                    // }

                    if (i > 0) {
                        result = values[i - 1] == values[k]? result + 1: result;
                    }
                }
            }
        }
        
        return result;
    }