点击获取AI摘要

2179. 统计数组中好三元组数目 H

给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的排列。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos $1_v$ 记为值 v 在 nums1 中出现的位置，pos $2_v$ 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos $1_x$ < pos $1_y$ < pos $1_z$ 和 pos $2_x$ < pos $2_y$ < pos $2_z$ 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。

示例 1：

输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos $1_x$ < pos $1_y$ < pos $1_z$ ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos $2_x$ < pos $2_y$ < pos $2_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 - 1
nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。

问题分析

题目给定两个长度为n且下标从0开始的整数数组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) ，要求返回好三元组的总数目。

算法思路

由于两个数组都是 0 到 n - 1 的排列，考虑以下转换：

构造新数组
我们先建立一个数组 p，其中

$p[i]=\text{pos2}[\text{nums1}[i]]$

这里的 $\text{pos2}[v]$ 表示值 $v$ 在 nums2 中的位置。
由于 nums1 本身已经按其在原数组中的顺序排序，因此原题中要求 “pos1 $x$ < pos1 $y$ < pos1 $z$ ” 已自动满足。问题就转化为：在数组 p 中计数满足

$p[i]<p[j]<p[k]$

且满足 $i<j<k$ 的三元组。
双遍扫描计数
对于数组中的每个中间元素 $p[j]$ ，设：
- $L_j$ ：在 $j$ 之前（即 $i<j$ ）满足 $p[i] < p[j]$ 的数量；
- $R_j$ ：在 $j$ 之后（即 $k>j$ ）满足 $p[k] > p[j]$ 的数量；
则以 $p[j]$ 为中间元素的有效三元组数量为 $L_j \times R_j$ 。整个三元组数量为所有 $j$ 上的累加和。
树状数组（Fenwick Tree）的作用
由于 $n$ 可能达到 $10^5$ 级别，直接遍历统计 $L_j$ 和 $R_j$ 是 $O(n^2)$ 的效率。借助树状数组，我们可以在 $O(\log n)$ 内查询某个前缀的值，从而：
- 正向遍历计算每个位置 $j$ 的 $L_j$ ；
- 逆向遍历计算每个位置 $j$ 的 $R_j$ 。

时间复杂度

构造映射与数组转换： $O(n)$
正序与逆序遍历树状数组操作：使用两个树状数组分别进行两次扫描(每个元素需要正向逆向各一次)，每个查询和更新均为 $O(\log n$ ，共计 $O(n \log n)$
总体时间复杂度： $O(n \log n)$
空间复杂度： $O(n)$ , 用于存储两个计数数组及树状数组的结构

代码分解

FenwickTree 类
负责单点更新和区间查询，从而在 $O(\log n)$ 时间内计算前缀和。

构造映射与数组转换
将 nums2 中每个数值映射到对应的位置，构造数组 p 后，数组 p 就是按照 nums1 顺序排列的 nums2 中的下标，即 p[i] 是 nums1 的第 i 个元素在 nums2 中的位置。

左侧计数（L[j]）
使用树状数组，从左到右扫描数组 p，对于每个位置 j，查询 p[j] 之前比它小的数字个数，并更新树状数组，通过遍历 p 数组并动态查询当前值之前的前缀和实现。

右侧计数（R[j]）
使用另一个树状数组，从右到左扫描数组 p，对于每个位置 j，查询已经处理的右侧元素中比 p[j] 大的数量，通过总已处理元素数减去小于等于 p[j] 的数目得到。

三元组数量累加
对每个中间位置 j，三元组数量为 $L[j] \times R[j]$ ，对所有可能的中间位置累加即为最终答案。

代码实现

class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)
    
    def update(self, index: int, delta: int):
        # index 从 0 开始转换到 1-based
        index += 1
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        # 查询前缀和 [0, index]，index 为 0-based
        index += 1
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

class Solution:
    @staticmethod
    def goodTriplets(nums1: list, nums2: list) -> int:
        n = len(nums1)
        
        # 建立 nums2 中值 -> 位置 的映射
        pos2 = [0] * n
        for idx, num in enumerate(nums2):
            pos2[num] = idx
        
        # 构造数组 p，其中 p[i] = pos2[nums1[i]]
        p = [pos2[num] for num in nums1]
        
        # 第一步：正序遍历，计算每个 j 左侧比 p[j] 小的数量 L[j]
        left_count = [0] * n
        fenwick_left = FenwickTree(n)
        for j in range(n):
            # p[j] 前有多少数比它小
            left_count[j] = fenwick_left.query(p[j] - 1)
            fenwick_left.update(p[j], 1)
        
        # 第二步：逆序遍历，计算每个 j 右侧比 p[j] 大的数量 R[j]
        right_count = [0] * n
        fenwick_right = FenwickTree(n)
        for j in range(n - 1, -1, -1):
            # 右侧比 p[j] 大的数量 = 当前已处理的个数中 p 值大于 p[j] 的数量
            # 先查询 p[j] 的前缀和，已加入的元素总数为 (n-1 - j)
            right_count[j] = fenwick_right.query(n - 1) - fenwick_right.query(p[j])
            fenwick_right.update(p[j], 1)
        
        # 三元组数量：对每个 j 中间元素，累加 L[j] * R[j]
        result = 0
        for j in range(n):
            result += left_count[j] * right_count[j]
        return result