class Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
}
};
2179. 统计数组中好三元组数目
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3] 输出：1 解释： 总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。 这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 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.length3 <= n <= 1050 <= nums1[i], nums2[i] <= n - 1nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。原站题解
python3 解法, 执行用时: 768 ms, 内存消耗: 32.4 MB, 提交时间: 2023-10-08 17:34:06
class Solution:
def goodTriplets1(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
p = [0] * n
for i, x in enumerate(nums1):
p[x] = i
ans = 0
tree = [0] * (n + 1)
for i in range(1, n - 1):
# 将 p[nums2[i - 1]] + 1 加入树状数组
j = p[nums2[i - 1]] + 1
while j <= n:
tree[j] += 1
j += j & -j
# 计算 less
y, less = p[nums2[i]], 0
j = y
while j:
less += tree[j]
j &= j - 1
ans += less * (n - 1 - y - (i - less))
return ans
# 引入 sortedList
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
from sortedcontainers import SortedList
n = len(nums1)
p = [0] * n
for i, x in enumerate(nums1):
p[x] = i
ans = 0
s = SortedList()
for i in range(1, n - 1):
s.add(p[nums2[i - 1]])
y = p[nums2[i]]
less = s.bisect_left(y)
ans += less * (n - 1 - y - (i - less))
return ans
golang 解法, 执行用时: 100 ms, 内存消耗: 10.6 MB, 提交时间: 2023-10-08 17:33:18
func goodTriplets(nums1, nums2 []int) (ans int64) {
n := len(nums1)
p := make([]int, n)
for i, v := range nums1 {
p[v] = i
}
tree := make([]int, n+1)
for i := 1; i < n-1; i++ {
for j := p[nums2[i-1]] + 1; j <= n; j += j & -j { // 将 p[nums2[i-1]]+1 加入树状数组
tree[j]++
}
y, less := p[nums2[i]], 0
for j := y; j > 0; j &= j - 1 { // 计算 less
less += tree[j]
}
ans += int64(less) * int64(n-1-y-(i-less))
}
return
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 80.4 MB, 提交时间: 2023-10-08 17:33:03
class Solution {
public:
long long goodTriplets(vector<int> &nums1, vector<int> &nums2) {
int n = nums1.size();
vector<int> p(n);
for (int i = 0; i < n; ++i)
p[nums1[i]] = i;
long long ans = 0;
vector<int> tree(n + 1);
for (int i = 1; i < n - 1; ++i) {
for (int j = p[nums2[i - 1]] + 1; j <= n; j += j & -j) // 将 p[nums2[i-1]]+1 加入树状数组
++tree[j];
int y = p[nums2[i]], less = 0;
for (int j = y; j; j &= j - 1) // 计算 less
less += tree[j];
ans += (long) less * (n - 1 - y - (i - less));
}
return ans;
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 55.4 MB, 提交时间: 2023-10-08 17:32:49
/**
* 等价转换 + 树状数组
*/
class Solution {
public long goodTriplets(int[] nums1, int[] nums2) {
var n = nums1.length;
var p = new int[n];
for (var i = 0; i < n; ++i)
p[nums1[i]] = i;
var ans = 0L;
var tree = new int[n + 1];
for (var i = 1; i < n - 1; ++i) {
for (var j = p[nums2[i - 1]] + 1; j <= n; j += j & -j) // 将 p[nums2[i-1]]+1 加入树状数组
++tree[j];
var y = p[nums2[i]];
var less = 0;
for (var j = y; j > 0; j &= j - 1) // 计算 less
less += tree[j];
ans += (long) less * (n - 1 - y - (i - less));
}
return ans;
}
}