本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
动态规划
本题其它解法
类似题解法
| 包括题目及代码 | C++二分查找算法：132 模式解法一枚举3 |
| C++二分查找算法：132 模式解法二枚举2 | |
| 代码简洁 | C++二分查找算法：132 模式解法三枚举1 |
| 性能最佳 | C++单调向量算法：132 模式解法三枚举1 |
| 代码更简洁 | C++二分查找算法：132模式枚举3简洁版 |
| 代码简洁，性能优越 | C++单调向量：132模式枚举1简洁版 |
题目
给你一个长度为 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 是一个排列。
第一版
分析
1324模式，第1的小在最前面，其次是第3小，再次是第2小的，最后是第4小的。
变量解释
| v21 | v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) |
| v32 | v32[i3][i2]=k，表示以num[i3]为3以nums[x]为2 组成的132模式的数量是k，x取[0,i2) |
代码
class Solution { public: long long countQuadruplets(vector& nums) { m_c = nums.size(); //v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) vector<vector> v21(m_c,vector(m_c+1)); for (int i2 = 0; i2 < m_c; i2++) { for (int i1 = 0; i1 < i2; i1++) { v21[i2][i1 + 1] = v21[i2][i1] + (nums[i1] < nums[i2]); } } vector<vector> v32(m_c, vector(m_c + 1)); for (int i3 = 0; i3 < m_c; i3++) { for (int i2 = i3 + 1; i2 < m_c; i2++) { v32[i3][i2 + 1] = v32[i3][i2]; if (nums[i3] > nums[i2]) { v32[i3][i2 + 1] += v21[i2][i3]; } } } long long llRet = 0; for (int i3 = 0; i3 < m_c; i3++) { for (int i4 = i3 + 1; i4 < m_c; i4++) { if (nums[i3] < nums[i4]) { llRet += v32[i3][i4]; } } } return llRet; } int m_c; };
测试用例
template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; vector<int> nums ; long long res; nums = { 1, 3, 2, 4, 5 }; res = slu.countQuadruplets(nums); Assert(2LL, res); nums = { 1, 2,3,4 }; res = slu.countQuadruplets(nums); Assert(0LL, res); nums = { 4,3,2,1 }; res = slu.countQuadruplets(nums); Assert(0LL, res); nums = { 4,3,2,6,5,1 }; res = slu.countQuadruplets(nums); Assert(0LL, res); nums = { 1,3,2,4 }; res = slu.countQuadruplets(nums); Assert(1LL, res); nums = { 2,1,4,3,5 }; res = slu.countQuadruplets(nums); Assert(2LL, res); nums.clear(); for (int i = 0; i < 4000; i++) { nums.emplace_back(i + 1); } res = slu.countQuadruplets(nums); Assert(0LL, res); //CConsole::Out(res); }
第二版
三步是如此相似，也许可以合并。第一步的循环似乎不同。我们把第一步的第一层循环换到第二层就更相似了。修改后的第一步：
for (int i1 = 0; i1 < m_c ; i1++) { for (int i2 = i1+1; i2 < m_c; i2++) { v21[i2][i1 + 1] = v21[i2][i1] + (nums[i1] < nums[i2]); } }
第三版
第一层 的循环变量改成i,第一层的循环变量改成j。
class Solution { public: long long countQuadruplets(vector<int>& nums) { m_c = nums.size(); //v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) vector<vector<int>> v21(m_c,vector<int>(m_c+1)); for (int i = 0; i < m_c ; i++) { for (int j = i+1; j < m_c; j++) { v21[j][i + 1] = v21[j][i] + (nums[i] < nums[j]); } } vector<vector<int>> v32(m_c, vector<int>(m_c + 1)); for (int i = 0; i < m_c; i++) { for (int j = i + 1; j < m_c; j++) { v32[i][j + 1] = v32[i][j]; if (nums[i] > nums[j]) { v32[i][j + 1] += v21[j][i]; } } } long long llRet = 0; for (int i = 0; i < m_c; i++) { for (int j = i + 1; j < m_c; j++) { if (nums[i] < nums[j]) { llRet += v32[i][j]; } } } return llRet; } int m_c; };
第四版
三轮循环合并。
class Solution { public: long long countQuadruplets(vector<int>& nums) { m_c = nums.size(); //v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) vector<vector<int>> v21(m_c,vector<int>(m_c+1)); vector<vector<int>> v32(m_c, vector<int>(m_c + 1)); long long llRet = 0; for (int i = 0; i < m_c ; i++) { for (int j = i+1; j < m_c; j++) { v21[j][i + 1] = v21[j][i] + (nums[i] < nums[j]); v32[i][j + 1] = v32[i][j]; if (nums[i] > nums[j]) { v32[i][j + 1] += v21[j][i]; } if (nums[i] < nums[j]) { llRet += v32[i][j]; } } } return llRet; } int m_c; };
第五版
v2 只用到三处, v21[j][i + 1] 和 v21[j][i]，可以简化成一维变量。
优化后，代码如下：
class Solution { public: long long countQuadruplets(vector<int>& nums) { m_c = nums.size(); //v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) vector<vector<int>> v32(m_c, vector<int>(m_c + 1)); long long llRet = 0; vector<int> v21(m_c); for (int i = 0; i < m_c ; i++) { for (int j = i+1; j < m_c; j++) { v32[i][j + 1] = v32[i][j]; if (nums[i] > nums[j]) { v32[i][j + 1] += v21[j]; } if (nums[i] < nums[j]) { llRet += v32[i][j]; } v21[j] += (nums[i] < nums[j]); } } return llRet; } int m_c; };
第六版
v32只用到v32[i][j + 1] v32[i][j]，我们可以简化成一个变量i32，i发生变化的时候赋初值0。
class Solution { public: long long countQuadruplets(vector<int>& nums) { m_c = nums.size(); //v21[i2][i1] = k，表示 nums[i2]和nums[x]组成12模式的数量是k，x取值范围[0,i1) long long llRet = 0; vector<int> v21(m_c); for (int i = 0; i < m_c ; i++) { int i32 = 0; for (int j = i+1; j < m_c; j++) { if (nums[i] < nums[j]) { llRet += i32; } if (nums[i] > nums[j]) { i32 += v21[j]; } v21[j] += (nums[i] < nums[j]); } } return llRet; } int m_c; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
