一、题目

给你一个整数数组 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）暴力法+记忆化

根据题目中对a和b的定义，可以使用最简单的三层for循环来确定i、j、k的值，根据定义求出a和b。
想要快速得出a和b的值，可以使用前缀异或值的记忆化，使用数组memo，memo[i]=arr[0] ^ arr[1] ^ … ^ arr[i - 1].

a = memo[i-1] ^ memo[j-1] b = memo[j-1] ^ memo[k]

2）两层循环方法

进一步理解题意，如果a==b，那么arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]^arr[j] ^ arr[j + 1] ^ … ^ arr[k]=0，也就是说，从i到k的所有元素异或值为0，那么只需要每当异或值为0时，就认定已经找到该三元组即可，无论j在(i, k]中哪个位置，都是满足题意的三元组，就找到了k-i个三元组。

三、代码

1）暴力法+记忆化

  1. class Solution {
  2.     public int countTriplets(int[] arr) {
  3.         int[] memo = new int[arr.length + 1];
  4.         for (int i = 1; i < memo.length; i++) {
  5.             memo[i] = memo[i-1] ^ arr[i-1];
  6.         }
  7.         int ans = 0;
  8.         for (int i = 1; i < memo.length - 1; i++) {
  9.             for (int j = i + 1; j < memo.length; j++) {
  10.                 for (int k = j; k < memo.length; k++) {
  11.                     int a = memo[i-1] ^ memo[j-1];
  12.                     int b = memo[j-1] ^ memo[k];
  13.                     if (a == b) {
  14.                         ans++;
  15.                     }
  16.                 }
  17.             }
  18.         }
  19.         return ans;
  20.     }
  21. }

时间复杂度为O(n)，空间复杂度为O(n)。

2）两层循环方法

  1. class Solution {
  2.     public int countTriplets(int[] arr) {
  3.         int ans = 0;
  4.         for (int i = 0; i < arr.length - 1; i++) {
  5.             int temp = arr[i];
  6.             for (int k = i+1; k < arr.length; k++) {
  7.                 temp ^= arr[k];
  8.                 if (temp == 0) {
  9.                     ans += k - i;
  10.                 }
  11.             }
  12.         }
  13.         return ans;
  14.     }
  15. }

时间复杂度为O(n)，空间复杂度为O(1)。