LeetCode 题解工作台
统计数组中好三元组数目
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。 好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1 v 记为值 v 在 n…
7
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
答案摘要
对于本题，我们先用 pos 记录每个数在 nums2 中的位置，然后依次对 nums1 中的每个元素进行处理。 考虑以当前数字作为三元组中间数字的好三元组的数目。第一个数字需要是之前已经遍历过的，并且在 nums2 中的位置比当前数字更靠前的；第三个数字需要是当前还没有遍历过的，并且在 nums2 中的位置比当前数字更靠后的。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你两个下标从 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]的排列。
解题思路
方法一：树状数组
对于本题，我们先用 pos 记录每个数在 nums2 中的位置，然后依次对 nums1 中的每个元素进行处理。
考虑以当前数字作为三元组中间数字的好三元组的数目。第一个数字需要是之前已经遍历过的，并且在 nums2 中的位置比当前数字更靠前的；第三个数字需要是当前还没有遍历过的，并且在 nums2 中的位置比当前数字更靠后的。
以 nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]为例，考虑我们的遍历过程：
- 首先处理 4，此时 nums2 中出现情况为
[4,X,X,X,X]，4 之前有值的个数是 0，4 之后没有值的个数有 4 个。因此以 4 为中间数字能形成 0 个好三元组。 - 接下来是 0，此时 nums2 中出现情况为
[4,X,0,X,X]，0 之前有值的个数是 1，0 之后没有值的个数有 2 个。因此以 0 为中间数字能形成 2 个好三元组。 - 接下来是 1，此时 nums2 中出现情况为
[4,1,0,X,X]，1 之前有值的个数是 1，0 之后没有值的个数有 2 个。因此以 1 为中间数字能形成 2 个好三元组。 - ...
- 最后是 2，此时 nums2 中出现情况为
[4,1,0,2,3]，2 之前有值的个数是 4，2 之后没有值的个数是 0。因此以 2 为中间数字能形成 0 个好三元组。
我们可以用树状数组来更新 nums2 中各个位置数字的出现情况，快速算出每个数字左侧 1 的个数，以及右侧 0 的个数。
树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：
- 单点更新
update(x, delta)： 把序列 x 位置的数加上一个值 delta； - 前缀和查询
query(x)：查询序列[1,...x]区间的区间和，即位置 x 的前缀和。
这两个操作的时间复杂度均为 。因此，整体的时间复杂度为 ，其中 为数组 的长度。空间复杂度 。
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
@staticmethod
def lowbit(x):
return x & -x
def update(self, x, delta):
while x <= self.n:
self.c[x] += delta
x += BinaryIndexedTree.lowbit(x)
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= BinaryIndexedTree.lowbit(x)
return s
class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
pos = {v: i for i, v in enumerate(nums2, 1)}
ans = 0
n = len(nums1)
tree = BinaryIndexedTree(n)
for num in nums1:
p = pos[num]
left = tree.query(p)
right = n - p - (tree.query(n) - tree.query(p))
ans += left * right
tree.update(p, 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n\times\log{n}) due to binary indexed tree queries and updates for each element. Space complexity is O(n) for mapping indices and auxiliary BIT arrays. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Check if candidate triplets satisfy order in both arrays instead of just one.
- question_mark
Expect O(n log n) solution using index mapping and efficient counting structures.
- question_mark
Be careful with off-by-one errors when transforming positions into counts for BIT.
常见陷阱
外企场景- error
Attempting a brute-force O(n^3) approach which will time out for n up to 10^5.
- error
Mixing positions of values instead of using consistent index mapping.
- error
Counting x, y, z independently without considering their relative order in both arrays.
进阶变体
外企场景- arrow_right_alt
Count good quadruplets instead of triplets with similar order constraints.
- arrow_right_alt
Arrays are not full permutations but contain distinct values in a limited range.
- arrow_right_alt
Instead of counting, return all good triplets explicitly (may need O(n^3) time).