统计数组中好三元组数目

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

给你两个下标从 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⁵
0 <= nums1[i], nums2[i] <= n - 1
nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long goodTriplets(vector<int>& nums1, vector<int>& nums2) { } };

typescript 解法, 执行用时: 34 ms, 内存消耗: 70.2 MB, 提交时间: 2025-04-15 09:14:05

class FenwickTree {
    private tree: number[];

    constructor(size: number) {
        this.tree = new Array(size + 1).fill(0);
    }

    update(index: number, delta: number): void {
        index++;
        while (index < this.tree.length) {
            this.tree[index] += delta;
            index += index & -index;
        }
    }

    query(index: number): number {
        index++;
        let res = 0;
        while (index > 0) {
            res += this.tree[index];
            index -= index & -index;
        }
        return res;
    }
}

function goodTriplets(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    const pos2 = new Array(n), reversedIndexMapping = new Array(n);;
    for (let i = 0; i < n; i++) {
        pos2[nums2[i]] = i;
    }
    for (let i = 0; i < n; i++) {
        reversedIndexMapping[pos2[nums1[i]]] = i;
    }
    const tree = new FenwickTree(n);
    let res = 0;
    for (let value = 0; value < n; value++) {
        const pos = reversedIndexMapping[value];
        const left = tree.query(pos);
        tree.update(pos, 1);
        const right = (n - 1 - pos) - (value - left);
        res += left * right;
    }
    return res;
}

rust 解法, 执行用时: 3 ms, 内存消耗: 5.2 MB, 提交时间: 2025-04-15 09:13:46

struct FenwickTree {
    tree: Vec<i32>,
}

impl FenwickTree {
    fn new(size: usize) -> Self {
        FenwickTree {
            tree: vec![0; size + 1],
        }
    }

    fn update(&mut self, index: usize, delta: i32) {
        let mut idx = index + 1;
        while idx < self.tree.len() {
            self.tree[idx] += delta;
            idx += idx & (!idx + 1);
        }
    }

    fn query(&self, index: usize) -> i32 {
        let mut idx = index + 1;
        let mut res = 0;
        while idx > 0 {
            res += self.tree[idx];
            idx -= idx & (!idx + 1);
        }
        res
    }
}

impl Solution {
    pub fn good_triplets(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
        let n = nums1.len();
        let mut pos2 = vec![0; n];
        for (i, &num) in nums2.iter().enumerate() {
            pos2[num as usize] = i;
        }
        let mut reversed_index_mapping = vec![0; n];
        for (i, &num) in nums1.iter().enumerate() {
            reversed_index_mapping[pos2[num as usize]] = i;
        }
        let mut tree = FenwickTree::new(n);
        let mut res = 0i64;
        for value in 0..n {
            let pos = reversed_index_mapping[value];
            let left = tree.query(pos) as i64;
            tree.update(pos, 1);
            let right = (n - 1 - pos) as i64 - (value as i64 - left);
            res += left * right;
        }
        res
    }
}

javascript 解法, 执行用时: 39 ms, 内存消耗: 70.3 MB, 提交时间: 2025-04-15 09:13:27

class FenwickTree {
    constructor(size) {
        this.tree = new Array(size + 1).fill(0);
    }

    update(index, delta) {
        index++;
        while (index < this.tree.length) {
            this.tree[index] += delta;
            index += index & -index;
        }
    }

    query(index) {
        index++;
        let res = 0;
        while (index > 0) {
            res += this.tree[index];
            index -= index & -index;
        }
        return res;
    }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var goodTriplets = function(nums1, nums2) {
    const n = nums1.length;
    const pos2 = new Array(n), reversedIndexMapping = new Array(n);;
    for (let i = 0; i < n; i++) {
        pos2[nums2[i]] = i;
    }
    for (let i = 0; i < n; i++) {
        reversedIndexMapping[pos2[nums1[i]]] = i;
    }
    const tree = new FenwickTree(n);
    let res = 0;
    for (let value = 0; value < n; value++) {
        const pos = reversedIndexMapping[value];
        const left = tree.query(pos);
        tree.update(pos, 1);
        const right = (n - 1 - pos) - (value - left);
        res += left * right;
    }
    return res;
};

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;
    }
}

上一题

下一题

详情