给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 \(pos1_v\) 记为值 v 在 nums1 中出现的位置，\(pos2_v\ 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 \(pos1_x < pos1_y < pos1_z\) 和 \(pos2_x < pos2_y < pos2_z\) 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入： nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出： 1
解释： 总共有 4 个三元组 (x,y,z) 满足 \(pos1_x < pos1_y < pos1_z\) ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。 这些三元组中，只有 (0,1,3) 满足 \(pos2_x < pos2_y < pos2_z\) 。所以只有 1 个好三元组。
示例 2：
输入： nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出： 4
解释： 总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。
提示：
n == nums1.length == nums2.length- \(3 <= n <= 10^5\)
0 <= nums1[i], nums2[i] <= n - 1nums1和nums2是[0, 1, ..., n - 1]的排列。- 对于每个值 y，如何找到值 x（0 ≤ x、 y≤ n-1）这样 x 在两个数组中都出现在 y 之前？
- 类似地，对于每个值 y，尝试查找值 z（0 ≤ y、 z≤ n-1），使 z 在两个数组中都出现在 y 之后。
- 现在，对于每个值 y，计算如果 y 被视为中间元素，可以形成的好三元组的数量。
题解
首先用哈希表记录每个数在数组二中的位置，然后按照数组一的顺序依次处理。
我们考虑以当前数字作为三元组中间数字的好三元组的数目。第一个数字需要是之前已经遍历过的，并且在数组二中的位置比当前数字更靠前的；第三个数字需要是当前还没有遍历过的，并且在数组二中的位置比当前数字更靠后的。这里只对数字的位置有要求，而对数字具体的值没有要求。
如何快速求出满足条件的第一个数字和第三个数字的个数呢？
以 [4,0,1,3,2][4,1,0,2,3]为例，考虑我们的遍历过程：
首先处理的是 4，此时数组二中的出现情况为：
[4,X,X,X,X]
我们需要统计的是 4 之前的有值的个数（0 个），以及 4 之后的没有值的个数（4 个）。因此以 4 为中间数字能形成 0 个好三元组。
接下来是 0，此时数组二中的出现情况为：
[4,X,0,X,X]
0 之前有值的个数（1 个），0 之后没有值的个数（2 个）。因此以 0 为中间数字能形成 2 个好三元组。
接下来是 1，此时数组二中的出现情况为：
[4,1,0,X,X]
1 之前有值的个数（1 个），1 之后没有值的个数（2 个）。因此以 1 为中间数字能形成 2 个好三元组。
接下来是 3，此时数组二中的出现情况为：
[4,1,0,X,3]
3 之前有值的个数（3 个），3 之后没有值的个数（0 个）。因此以 3 为中间数字能形成 0 个好三元组。
最后是 2，此时数组二中的出现情况为：
[4,1,0,2,3]
2 之前有值的个数（3 个），2 之后没有值的个数（0 个）。因此以 2 为中间数字能形成 0 个好三元组。
最后的答案是 4。
因为我们并不关心数字具体的值，而只关心是否出现过，所以我们实际上可以把数组二的出现情况用一个 0–1 数组来表示：
[1,0,0,0,0]→[1,0,1,0,0]→[1,1,1,0,0]→[1,1,1,0,1]→[1,1,1,1,1]
这时可以看出，我们用树状数组（或者线段树、平衡树）就能快速更新状态，并求出我们需要的两个数值（左边的 1 的个数和右边的 0 的个数）。
理清思路之后，代码的实现是比较容易的。
- 时间复杂度 O(NlogN)。
- 空间复杂度 O(N)。
template <class T> class FenwickTree {
int limit;
vector<T> arr;
int lowbit(int x) { return x & (-x); }
public:
FenwickTree(int limit) {
this->limit = limit;
arr = vector<T>(limit + 1);
}
void update(int idx, T delta) {
for (; idx <= limit; idx += lowbit(idx))
arr[idx] += delta;
}
T query(int idx) {
T ans = 0;
for (; idx > 0; idx -= lowbit(idx))
ans += arr[idx];
return ans;
}
};
class Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
FenwickTree<int> occur(n);
unordered_map<int, int> pos;
for (int i = 0; i < n; ++i)
pos[nums2[i]] = i + 1;
long long ans = 0;
for (int i = 0; i < n; ++i) {
int idx = pos[nums1[i]];
int left = occur.query(idx);
int right = n - idx - (occur.query(n) - occur.query(idx));
ans += 1LL * left * right;
occur.update(idx, 1);
}
return ans;
}
};