枚举，LeetCode 2552. 统计上升四元组

一、题目

1、题目描述

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

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

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

2、接口描述

python3

 ​

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

cpp

 ​

class Solution {
public:long long countQuadruplets(vector<int>& nums) {}
};

C#

 ​

public class Solution {public long CountQuadruplets(int[] nums) {}
}

3、原题链接

---

二、解题报告

1、思路分析

可以用递推预处理前后缀，但是枚举的方式更训练思维

记cnt4 为 l 的数目

我们考虑 枚举 l，维护cnt3[]，即 [0, l) 内 (i, j, k) 的数目

在内层枚举 j，维护cnt2，即[0, j] 内 (i, k) 的数目

如果nums[j] < nums[k]

则 cnt4 += cnt3[j]，cnt2 += 1

否则

cnt3[j] += cnt2，因为cnt2 为 (i, k) 的数目，i  < j，k = l  > i 故合法

2、复杂度

时间复杂度： O(N^2)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:def countQuadruplets(self, nums: List[int]) -> int:cnt4 = 0n = len(nums)cnt3 = [0] * nfor l in range(2, n):cnt2 = 0for j in range(l):if nums[j] < nums[l]:cnt4 += cnt3[j]cnt2 += 1else:cnt3[j] += cnt2return cnt4

cpp

 ​

using i64 = long long;
class Solution {
public:long long countQuadruplets(vector<int>& nums) {i64 cnt4 = 0;int n = nums.size();std::vector<i64> cnt3(n);for (int l = 2, cnt2 = 0; l < n; ++ l) {cnt2 = 0;for (int j = 0; j < l; ++ j) {if (nums[j] < nums[l])cnt4 += cnt3[j], ++ cnt2;else cnt3[j] += cnt2;}}return cnt4;}
};

C#

 ​

public class Solution
{public long CountQuadruplets(int[] nums){int n = nums.Length;long[] cnt3 = new long[n];long cnt4 = 0;for (int l = 2, cnt2 = 0; l < n; ++ l){cnt2 = 0;for (int j = 0; j < l; ++ j){if (nums[j] < nums[l]){cnt4 += cnt3[j];++cnt2;}else{cnt3[j] += cnt2;}}}return cnt4;}
}