2552.统计上升四元组

链接：2552.统计上升四元组
难度：Hard
标签：树状数组、数组、动态规划、枚举、前缀和
简介：给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

题解 1 - cpp

• 编辑时间：2023-02-01
• 执行用时：272ms
• 内存消耗：10.6MB
• 编程语言：cpp
• 解法介绍：枚举l，对于每一个l，查找可能的j，记录j的132模式个数，即i<j<k&&v[i]<v[k]<v[j]。

class Solution {
public:
    typedef long long ll;
    ll countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        ll ans = 0;
        vector<int> list(n, 0);
        for (int l = 0; l < n; l++) {
            for (int j = 0; j < l - 1; j++) {
                if (nums[j] < nums[l]) ans += list[j];
            }
            for (int j = 0, cnt = 0; j < l; j++) {
                if (nums[j] > nums[l]) list[j] += cnt;
                if (nums[j] < nums[l]) cnt++;
            }
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-02-01
• 执行用时：2284ms
• 内存消耗：15.2MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        list = [0] * n
        for l in range(n):
            for j in range(l):
                if nums[j] < nums[l]:
                    ans += list[j]
            cnt = 0
            for j in range(l):
                if nums[j] > nums[l]:
                    list[j] += cnt
                if nums[j] < nums[l]:
                    cnt += 1
        return ans

题解 3 - rust

• 编辑时间：2023-02-01
• 执行用时：72ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_quadruplets(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut list = vec![0; n];
        let mut ans = 0;
        for l in 0..n {
            for j in 0..l {
                if nums[j] < nums[l] {
                    ans += list[j];
                }
            }
            let mut cnt = 0;
            for j in 0..l {
                if nums[j] > nums[l] {
                    list[j] += cnt;
                }
                if nums[j] < nums[l] {
                    cnt += 1;
                }
            }
        }
        ans
    }
}

题解 4 - python

• 编辑时间：2024-09-10
• 执行用时：2666ms
• 内存消耗：16.88MB
• 编程语言：python
• 解法介绍：定义三元组为i<j<k&&v[i]<v[k]<v[j]，遍历时同时记录前面的三元组数量，以及当前节点当k位置时的数量。

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        arr = [0] * n
        res = 0
        for l in range(n):
            for j in range(l - 1):
                if nums[j] < nums[l]:
                    res += arr[j]
            cnt = 0
            for j in range(l):
                if nums[j] > nums[l]:
                    arr[j] += cnt
                if nums[j] < nums[l]:
                    cnt += 1
        return res