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

## [1442] 形成两个异或相等数组的三元组数目

[力扣原题链接](https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/)

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

<pre>输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
</pre>

**示例 2：**

**示例 3：**

**示例 4：**

**示例 5：**

**提示：**

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

### 题解

傻瓜式题解：直接暴力算出数组所有三数子集，计算每次的子集是否符合 a == b。使用递归写法，代码等价于三重循环。
其实不需要使用三重循环。由题 a == b ==> arr[i] ^ arr[i + 1] ^ .. ^ arr[ j - 1] = arr[j] ^ arr[j + 1] .. ^ arr[k],由异或性质，该式等价于arr[i] ^ arr[i + 1] ^ ..  =arr[ j - 1] ^ arr[j] ^ arr[j + 1] .. ^ arr[k] 。也就是说j可以是i,k中的任意一值。可调整为双重循环。力扣题解中还有使用哈希表优化为一重循环。
[力扣题解](https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/solution/xing-cheng-liang-ge-yi-huo-xiang-deng-sh-jud0/)

### 代码

```cpp
class Solution {
public:
 vector<int> xor_num_list;

int getXorNum(vector<int> &arr,int i,int k)
 {
 if(xor_num_list.empty())
 {
 int being_num = 0;
 xor_num_list.push_back(being_num); //第一个值为0
 for(int i = 0; i < (int)arr.size(); ++i)
 {
 being_num ^= arr[i];
 xor_num_list.push_back(being_num);
 }
 }

if(i > k || i < 0 || i > (int)xor_num_list.size() || k < 0 || k >= (int)xor_num_list.size()) return 0;

return (xor_num_list[k + 1] ^ xor_num_list[i]);
    }

void countHelper(vector<int>& arr,vector<int>& cur_arr,int &count,int begin_index)
 {
 if(begin_index >= (int)arr.size() || (int)cur_arr.size() >= 3) return;

if((int)cur_arr.size() == 1) begin_index ++; //特殊处理：i < j <= k
 for(int i = begin_index; i < (int)arr.size(); ++i)
 {
 cur_arr.push_back(i);

if((int)cur_arr.size() == 3)     //达到3数  判断是否相等
            {
                if(getXorNum(arr,cur_arr[0],cur_arr[1] - 1) == getXorNum(arr,cur_arr[1],cur_arr[2]))
                {
                    count ++;
                }
            }
            else  //计算下一个数
            {
                countHelper(arr,cur_arr,count,i);
            }

cur_arr.pop_back();   //回溯
        }
    }

int countTriplets(vector<int>& arr) {
 xor_num_list.clear();
 int count = 0;
 vector<int> cur_arr;
 countHelper(arr,cur_arr,count,0);
 return count;
 }
};
```