Medium

题目描述

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

提示：

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

解题思路

解题思路

这道题的关键在于理解异或运算的性质。当 a == b 时，有：

arr[i] ^ arr[i+1] ^ ... ^ arr[j-1] == arr[j] ^ arr[j+1] ^ ... ^ arr[k]

根据异或运算的性质，如果两个数相等，那么它们的异或值为 0。因此：

(arr[i] ^ arr[i+1] ^ ... ^ arr[j-1]) ^ (arr[j] ^ arr[j+1] ^ ... ^ arr[k]) = 0

这等价于：

arr[i] ^ arr[i+1] ^ ... ^ arr[k] = 0

所以问题转化为：寻找所有异或值为 0 的子数组，然后统计可能的分割方式。

方法一：暴力枚举（O(n³)）

直接枚举所有可能的 i, j, k 组合，计算对应的异或值并判断是否相等。

方法二：前缀异或优化（O(n²)）【推荐】

使用前缀异或数组优化计算。对于任意子数组 [i, k]，如果其异或值为 0，那么在这个子数组中，j 可以取 i+1 到 k 之间的任意值，共有 k-i 种选择。

关键观察：如果 prefix[i] == prefix[k+1]，那么子数组 [i, k] 的异或值为 0。

代码实现

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        int count = 0;
        
        // 计算前缀异或数组
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        // 枚举所有可能的子数组起点和终点
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                // 如果子数组[i, k]的异或值为0
                if (prefix[i] == prefix[k + 1]) {
                    // j可以取i+1到k之间的任意值
                    count += k - i;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        n = len(arr)
        count = 0
        
        # 计算前缀异或数组
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ arr[i]
        
        # 枚举所有可能的子数组起点和终点
        for i in range(n):
            for k in range(i + 1, n):
                # 如果子数组[i, k]的异或值为0
                if prefix[i] == prefix[k + 1]:
                    # j可以取i+1到k之间的任意值
                    count += k - i
        
        return count

public class Solution {
    public int CountTriplets(int[] arr) {
        int n = arr.Length;
        int count = 0;
        
        // 计算前缀异或数组
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        // 枚举所有可能的子数组起点和终点
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                // 如果子数组[i, k]的异或值为0
                if (prefix[i] == prefix[k + 1]) {
                    // j可以取i+1到k之间的任意值
                    count += k - i;
                }
            }
        }
        
        return count;
    }
}

var countTriplets = function(arr) {
    let count = 0;
    const n = arr.length;
    
    for (let i = 0; i < n; i++) {
        let xor = 0;
        for (let k = i; k < n; k++) {
            xor ^= arr[k];
            if (xor === 0 && k > i) {
                count += k - i;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
前缀异或优化O(n²)O(n)
暴力枚举O(n³)O(1)

相关题目