题目描述

给你一个整数数组 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) 的数目。

样例

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

输入：arr = [1,1,1,1,1]
输出：10

输入：arr = [2,3]
输出：0

输入：arr = [1,3,5,7,9]
输出：3

输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8

限制

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

算法1

(前缀和，暴力枚举) $O(n^3)$

1. 先求出原数组的前缀异或和数组 s。利用异或的性质，a 和 b 分别为 s[j - 1] ^ s[i - 1] 和 s[k] ^ s[j - 1]。
2. 暴力枚举 i, j, k 然后统计答案。

时间复杂度

• 求前缀和的时间复杂度为 $O(n)$，暴力枚举的时间复杂度为 $O(n^3)$，故总时间复杂度为 $O(n^3)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储前缀和数组。

C++ 代码

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        vector<int> s(n + 1);
        s[0] = 0;

        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] ^ arr[i - 1];

        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                for (int k = j; k <= n; k++)
                    if (s[j - 1] ^ s[i - 1] == s[k] ^ s[j - 1])
                        ans++;

        return ans;
    }
};

算法2

(前缀和，哈希表) $O(n^2)$

1. 在算法 1 的基础上，用哈希表记录以每个位置 j 结尾，每个区间 [i, j] 异或和的出现的次数。
2. 枚举 k，然后枚举 j，直接累计区间 [j, k] 异或和以 j - 1 结尾的哈希值。

时间复杂度

• 求前缀和的时间复杂度为 $O(n)$，维护哈希表的时间复杂度为 $O(n^2)$，枚举的时间复杂度为 $O(n^2)$，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间存储前缀和数组和哈希表。

C++ 代码

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();
        vector<int> s(n + 1);
        s[0] = 0;

        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] ^ arr[i - 1];

        int ans = 0;
        vector<unordered_map<int, int>> mp(n + 1);

        for (int j = 1; j <= n; j++)
            for (int i = 1; i <= j; i++)
                mp[j][s[j] ^ s[i - 1]]++;

        for (int k = 1; k <= n; k++)
            for (int j = 1; j <= k; j++)
                ans += mp[j - 1][s[k] ^ s[j - 1]];

        return ans;
    }
};

算法3

(异或的性质) $O(n^2)$

1. 通过异或的性质，a = [i, j - 1] 的异或和可以写成 [0, i - 1] ^ [0, j - 1]。b = [j, k] 的异或和可以写成 [0, k] ^ [0, j - 1]。
2. 如果存在 i 和 k，满足 [0, i - 1] == [0, k]（如果 i 是 0 则定义 [0, -1] 的异或和为 0），则可以推出对于所有的 j 满足 i + 1 <= j <= k，都有 a == b。
3. 所以我们可以枚举 i 和 k，然后统计答案。

时间复杂度

• 两重循环，时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();

        int x = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            int t = x;
            for (int k = i; k < n; k++) {
                t ^= arr[k];
                if (t == x)
                    ans += k - i;
            }
            x ^= arr[i];
        }

        return ans;
    }
};

算法4

(异或的性质，哈希表) $O(n)$

1. 用哈希表优化算法 3，哈希表记录异或值为 x 的下标总和以及个数。
2. 我们在枚举 k 的过程中不断更新哈希表，如果我们发现了 [0, k] 的异或和在哈希表中出现了，则借用算法 3 的计算公式，快速的算出所有合法 i 贡献的答案。

时间复杂度

• 每次维护哈希表的时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要的 $O(n)$ 额外空间存储哈希表。

C++ 代码

class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int n = arr.size();

        unordered_map<int, pair<int, int>> mp;

        mp[0] = make_pair(0, 1);

        int x = 0, ans = 0;
        for (int k = 0; k < n; k++) {
            x ^= arr[k];

            if (mp.find(x) != mp.end())
                ans += k * mp[x].second - mp[x].first;

            mp[x].first += k + 1;
            mp[x].second++;
        }

        return ans;
    }
};