2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。 它包含 1 到 n 的所有数字，请

2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。

它包含 1 到 n 的所有数字，请你返回上升四元组的数目。

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

0

nums[i] < nums[k] < nums[j] < nums[l] 。

输入：nums = [1,3,2,4,5]。

输出：2。

来自左程云。

答案2023-11-22：

go代码用灵捷3.5编写。

rust代码用讯飞星火编写。

c++的代码用天工编写。

灵捷3.5本来用起来还可以，但有次数限制，故放弃。

大体过程如下：

算法1：countQuadruplets1

1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。

2.遍历数组，从第二个元素开始（下标为1）：

a.初始化计数器cnt为0。

b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1。

c.再次遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将cnt加到dp[j]上；否则，将dp[j]加上cnt的整数值。

3.返回ans作为结果。

算法2：countQuadruplets2

1.初始化变量：n为数组长度，ans为结果计数器，dp为动态规划数组。

2.遍历数组，从第二个元素开始（下标为1）：

a.初始化计数器cnt为0。

b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将dp[j]加到ans上，并将cnt加1；否则，将dp[j]加上cnt的整数值。

3.返回ans作为结果。

总的时间复杂度：两种算法的时间复杂度都是O(n^2)，因为需要两层循环遍历数组。

总的额外空间复杂度：两种算法的空间复杂度都是O(n)，因为需要使用一个长度为n的动态规划数组dp。

go完整代码如下：

package main

import "fmt"

func countQuadruplets1(nums []int) int64 {

n := len(nums)

var ans int64

dp := make([]int64, n)

for l := 1; l 

cnt := 0

for j := 0; j 

if nums[j] 

ans += dp[j]

}

}

cnt = 0

for j := 0; j 

if nums[j] 

cnt++

} else {

dp[j] += int64(cnt)

}

}

}

return ans

}

func countQuadruplets2(nums []int) int64 {

n := len(nums)

var ans int64

dp := make([]int64, n)

for l := 1; l 

cnt := 0

for j := 0; j 

if nums[j] 

ans += dp[j]

cnt++

} else {

dp[j] += int64(cnt)

}

}

}

return ans

}

func main() {

nums := []int{1, 3, 2, 4, 5}

fmt.Println(countQuadruplets1(nums))

fmt.Println(countQuadruplets2(nums))

}

在这里插入图片描述rust完整代码如下：

fn count_quadruplets1(nums: Vec) -> i64 {

let n = nums.len();

let mut ans = 0;

let mut dp = vec![0; n];

for l in 1..n {

let mut cnt = 0;

for j in 0..l {

if nums[j] 

ans += dp[j];

cnt += 1;

} else {

dp[j] += cnt;

}

}

}

ans as i64

}

fn count_quadruplets2(nums: Vec) -> i64 {

let n = nums.len();

let mut ans = 0;

let mut dp = vec![0; n];

for l in 1..n {

let mut cnt = 0;

for j in 0..l {

if nums[j] 

ans += dp[j];

cnt += 1;

} else {

dp[j] += cnt;

}

}

}

ans as i64

}

fn main() {

let nums = vec![1, 3, 2, 4, 5];

println!("count_quadruplets1: {}", count_quadruplets1(nums));

let nums = vec![1, 3, 2, 4, 5];

println!("count_quadruplets2: {}", count_quadruplets2(nums));

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

using namespace std;

long long countQuadruplets1(vector& nums) {

int n = nums.size();

long long ans = 0;

vector dp(n, 0);

for (int l = 1; l 

for (int j = 0; j 

if (nums[j] 

ans += dp[j];

}

}

int cnt = 0;

for (int j = 0; j 

if (nums[j] 

cnt++;

}

else {

dp[j] += cnt;

break;

}

}

}

return ans;

}

long long countQuadruplets2(vector& nums) {

int n = nums.size();

long long ans = 0;

vector dp(n, 0);

for (int l = 1; l 

int cnt = 0;

for (int j = 0; j 

if (nums[j] 

ans += dp[j];

cnt++;

}

else {

dp[j] += cnt;

}

}

}

return ans;

}

int main() {

vector nums = { 1, 3, 2, 4, 5 };

cout 

cout 

return 0;

}

在这里插入图片描述