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 是一个排列。

解题思路

这道题要求找到满足特定条件的四元组数量。关键观察是四元组的值需要满足 nums[i] < nums[k] < nums[j] < nums[l] 且位置关系为 i < j < k < l。

解法思路

核心思想： 枚举中间两个位置 j 和 k，然后分别计算满足条件的 i 和 l 的数量。

对于固定的 j 和 k（其中 j < k），我们需要：

  • 在位置 j 左侧找到所有满足 nums[i] < nums[k] 的位置 i
  • 在位置 k 右侧找到所有满足 nums[l] > nums[j] 的位置 l
  • 同时还要保证 nums[k] < nums[j]

预处理优化：

  1. prefix[j][k]：表示在位置 j 左侧且值小于 nums[k] 的元素个数
  2. suffix[k][j]：表示在位置 k 右侧且值大于 nums[j] 的元素个数

算法步骤：

  1. 预计算 prefix 数组：对于每个位置 j，计算其左侧小于各个值的元素个数
  2. 预计算 suffix 数组：对于每个位置 k，计算其右侧大于各个值的元素个数
  3. 枚举所有 j < k 的组合，如果 nums[k] < nums[j]，则累加 prefix[j][nums[k]] * suffix[k][nums[j]]

时间复杂度为 O(n²)，空间复杂度为 O(n²)。

代码实现

class Solution {
public:
    long long countQuadruplets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> prefix(n, vector<int>(n + 1, 0));
        vector<vector<int>> suffix(n, vector<int>(n + 1, 0));
        
        // 预计算prefix数组：prefix[j][val]表示在位置j左侧小于val的元素个数
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                for (int val = nums[i] + 1; val <= n; val++) {
                    prefix[j][val]++;
                }
            }
        }
        
        // 预计算suffix数组：suffix[k][val]表示在位置k右侧大于val的元素个数
        for (int k = 0; k < n; k++) {
            for (int l = k + 1; l < n; l++) {
                for (int val = 1; val < nums[l]; val++) {
                    suffix[k][val]++;
                }
            }
        }
        
        long long result = 0;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[k] < nums[j]) {
                    result += (long long)prefix[j][nums[k]] * suffix[k][nums[j]];
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [[0] * (n + 1) for _ in range(n)]
        suffix = [[0] * (n + 1) for _ in range(n)]
        
        # 预计算prefix数组：prefix[j][val]表示在位置j左侧小于val的元素个数
        for j in range(n):
            for i in range(j):
                for val in range(nums[i] + 1, n + 1):
                    prefix[j][val] += 1
        
        # 预计算suffix数组：suffix[k][val]表示在位置k右侧大于val的元素个数
        for k in range(n):
            for l in range(k + 1, n):
                for val in range(1, nums[l]):
                    suffix[k][val] += 1
        
        result = 0
        for j in range(n):
            for k in range(j + 1, n):
                if nums[k] < nums[j]:
                    result += prefix[j][nums[k]] * suffix[k][nums[j]]
        
        return result

public class Solution {
    public long CountQuadruplets(int[] nums) {
        int n = nums.Length;
        int[,] prefix = new int[n, n + 1];
        int[,] suffix = new int[n, n + 1];
        
        // 预计算prefix数组：prefix[j,val]表示在位置j左侧小于val的元素个数
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < j; i++) {
                for (int val = nums[i] + 1; val <= n; val++) {
                    prefix[j, val]++;
                }
            }
        }
        
        // 预计算suffix数组：suffix[k,val]表示在位置k右侧大于val的元素个数
        for (int k = 0; k < n; k++) {
            for (int l = k + 1; l < n; l++) {
                for (int val = 1; val < nums[l]; val++) {
                    suffix[k, val]++;
                }
            }
        }
        
        long result = 0;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[k] < nums[j]) {
                    result += (long)prefix[j, nums[k]] * suffix[k, nums[j]];
                }
            }
        }
        
        return result;
    }
}

var countQuadruplets = function(nums) {
    const n = nums.length;
    const prefix = Array(n).fill().map(() => Array(n + 1).fill(0));
    const suffix = Array(n).fill().map(() => Array(n + 1).fill(0));
    
    // 预计算prefix数组：prefix[j][val]表示在位置j左侧小于val的元素个数
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < j; i++) {
            for (let val = nums[i] + 1; val <= n; val++) {
                prefix[j][val]++;
            }
        }
    }
    
    // 预计算suffix数组：suffix[k][val]表示在位置k右侧大于val的元素个数
    for (let k = 0; k < n; k++) {
        for (let l = k + 1; l < n; l++) {
            for (let val = 1; val < nums[l]; val++) {
                suffix[k][val]++;
            }
        }
    }
    
    let result = 0;
    for (let j = 0; j < n; j++) {
        for (let k = j + 1; k < n; k++) {
            if (nums[k] < nums[j]) {
                result += prefix[j][nums[k]] * suffix[k][nums[j]];
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)预处理prefix和suffix数组各需要O(n³)时间，枚举j,k需要O(n²)时间
空间复杂度O(n²)需要两个n×(n+1)的二维数组存储prefix和suffix信息

相关题目