题目描述
给你两个下标从 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)
。
请你返回好三元组的 总数目。
样例
输入: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 个好三元组。
输入: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 - 1
nums1
和nums2
是[0, 1, ..., n - 1]
的排列。
算法
(树状数组) $O(n \log n)$
- 第一轮,按照
nums1
规定的 优先级,统计出nums2
中每个数字,其可以与前序数字组成合法数对的方案数。 - 第二轮,仍然按照
nums1
的优先级,统计出nums2
中每个数字,其可以与前序某个数字组成合法三元组的方案数。
时间复杂度
- 每一轮都需要 $O(n \log n)$ 的时间使用树状数组统计,故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储树状数组以及临时数组。
C++ 代码
#define LL long long
const int N = 100010;
class Solution {
private:
int n;
LL f[N];
void add(int x, LL y) {
for (; x <= n; x += x & -x)
f[x] += y;
}
LL query(int x) {
LL tot = 0;
for (; x; x -= x & -x)
tot += f[x];
return tot;
}
public:
LL goodTriplets(vector<int>& nums1, vector<int>& nums2) {
n = nums1.size();
vector<int> p(n);
for (int i = 0; i < n; i++)
p[nums1[i]] = i + 1;
for (int i = 1; i <= n; i++)
f[i] = 0;
vector<int> s(n);
for (int i = 0; i < n; i++) {
s[i] = query(p[nums2[i]] - 1);
add(p[nums2[i]], 1);
}
for (int i = 1; i <= n; i++)
f[i] = 0;
LL ans = 0;
for (int i = 0; i < n; i++) {
ans += query(p[nums2[i]] - 1);
add(p[nums2[i]], s[i]);
}
return ans;
}
};