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

发表于 更新于 分类于 阅读次数：

题目链接：LeetCode 1442 - 形成两个异或相等数组的三元组数目

记 \(S_i\) 为 \(x_0\) 到 \(x_i\) 的 \(\rm xor\) 和。

如果 \(S_i = S_j\)，那么说明 \([i - 1, j]\) 区间的 \(\rm xor\) 和为 \(0\)，这个区间对答案的贡献为 \(j - i - 1\)。

假设 \(S\) 序列中值为 \(t\) 的数字的位置组成了序列 \(p_0, p_2, p_3, ..., p_{n - 1}\)

那么 \(t\) 对应的这个序列对答案的贡献是：

\[ \begin{aligned} & \sum_{i = 0}^{n - 1} \sum_{j = 0}^{i - 1} p_i - p_j - 1 \\ = & \sum_{i = 0}^{n - 1} \left[ \sum_{j = 0}^{i - 1} p_i - \sum_{j = 0}^{i - 1} p_j - \sum_{j = 0}^{i - 1} 1 \right] \\ = & \sum_{i = 0}^{n - 1} \left[ i \times p_i - \sum_{j = 0}^{i - 1} p_j - i \right] \end{aligned} \]

其中 \(\sum_{j = 0}^{i - 1} p_j\) 可以在线性的时间内预处理出来，或者对 \(i\) 枚举的时候直接算。

于是上面这个算式就可以在线性时间内算出来。

对每个 \(t\)，都算这个式子。

时间 / 空间都是 \(O(n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<int, vector<int>> h;
    int countTriplets(vector<int>& arr) {
        h[0].push_back(-1);
        int cur_xor_sum = 0, i = 0;
        for (const auto &x: arr) {
            cur_xor_sum ^= x;
            h[cur_xor_sum].push_back(i);
            ++i;
        }

        int ans = 0;
        for (const auto &[k, v]: h) {
            int n = v.size(), pre = 0;
            for (int i = 0; i < n; ++i) {
                ans += i * v[i] - pre - i;
                pre += v[i];
            }
        }

        return ans;
    }
};