统计上升四元组

难度: Hard

给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：

0 <= i < j < k < l < n 且
nums[i] < nums[k] < nums[j] < nums[l] 。

示例 1：

输入：nums = [1,3,2,4,5]
输出：2
解释：
- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] < nums[k] < nums[j] < nums[l] 。
没有其他的四元组，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4]
输出：0
解释：只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] < nums[k] ，所以我们返回 0 。

提示：

4 <= nums.length <= 4000
1 <= nums[i] <= nums.length
nums 中所有数字 互不相同 ，nums 是一个排列。

Submission

运行时间: 68 ms

内存: 17.7 MB

class Solution:
    def countQuadruplets(self, a: List[int]) -> int:

        ans = 0

        n = len(a)

        cnt = [0]*n

        for l in range (0,n):

            x = 0

            for j in range (0,l):

                if a[j] < a[l]:

                    ans += cnt[j]

                    x += 1

                else:

                    cnt[j]+= x

        return ans

Explain

题解采用了一种高效的方法来计算数组中的特定四元组的数量。整体思路是利用一个计数数组 cnt 来存储特定条件下的计数。对于每个位置 l，我们遍历所有 j（j < l），检查 a[j] 是否小于 a[l]。如果条件满足，则将 cnt[j] 的值累加到结果 ans 上，并且将 x（x 记录从 0 到当前 j 的满足条件 a[i] < a[k] < a[j] 的数量）累加 1。如果条件不满足，则将 x 的值累加到 cnt[j] 上，这样在未来的遍历中，当遇到适合的 a[l] 时，可以直接利用 cnt[j] 来更新答案。这种方法巧妙地避免了四重循环，通过三重循环和巧妙的统计优化了计算。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def countQuadruplets(self, a: List[int]) -> int:

        ans = 0  # 初始化答案计数

        n = len(a)  # 数组长度

        cnt = [0] * n  # 初始化计数数组

        for l in range(0, n):  # 遍历每个位置作为 l

            x = 0  # 初始化 x

            for j in range(0, l):  # 遍历每个位置作为 j，j 必须小于 l

                if a[j] < a[l]:  # 检查是否满足 a[j] < a[l]

                    ans += cnt[j]  # 更新答案

                    x += 1  # 更新 x

                else:

                    cnt[j] += x  # 将 x 加到 cnt[j]

        return ans  # 返回统计的四元组数量

Explore

在题解中，计数数组 cnt[j] 存储的是对于每个固定的 j，满足 i < j < k < l 和 nums[i] < nums[k] < nums[j] < nums[l] 条件的 i 和 k 的组合数量。这样的设置是为了在遍历到 l 时，能够直接利用 cnt[j] 来统计满足条件的四元组数量，从而避免重复的四重遍历。

在 a[j] < a[l] 的条件下将 x 累加到 cnt[j] 上，是因为 x 记录的是从位置 0 到当前 j 之间，满足 nums[i] < nums[k] < nums[j] 的二元组 (i, k) 的数量。当我们确认 nums[j] < nums[l] 时，意味着这些二元组 (i, k) 可以与当前的 j 和 l 形成满足条件的四元组。因此，我们将这个数量累加到 cnt[j] 中，以便后续可以直接使用，这样做主要是为了优化计算效率，避免重复计算已经统计过的组合数量。

题解采用的方法可以确保每个四元组都是唯一的，没有重复计算。这是因为在遍历过程中，每个元素的位置 i, j, k, l 都严格按照 i < j < k < l 的顺序来选取，且 nums 的条件也严格按照 nums[i] < nums[k] < nums[j] < nums[l] 来检查。通过这种方式，每个四元组的组合都是唯一确定的，不存在位置或值的重复，从而确保了四元组的唯一性。