统计上升四元组

Given a 0-indexed integer array nums of size n containing all numbers from 1 to n, return the number of increasing quadruplets.

A quadruplet (i, j, k, l) is increasing if:

• 0 <= i < j < k < l < n, and
• nums[i] < nums[k] < nums[j] < nums[l].

 

Example 1:

Input: nums = [1,3,2,4,5]
Output: 2
Explanation: 
- When i = 0, j = 1, k = 2, and l = 3, nums[i] < nums[k] < nums[j] < nums[l].
- When i = 0, j = 1, k = 2, and l = 4, nums[i] < nums[k] < nums[j] < nums[l]. 
There are no other quadruplets, so we return 2.

Example 2:

Input: nums = [1,2,3,4]
Output: 0
Explanation: There exists only one quadruplet with i = 0, j = 1, k = 2, l = 3, but since nums[j] < nums[k], we return 0.

 

Constraints:

• 4 <= nums.length <= 4000
• 1 <= nums[i] <= nums.length
• All the integers of nums are unique. nums is a permutation.

/*
 * 思路：
 * 使用Java Stream API来处理数组中的每个元素。
 * 虽然Stream API不能直接处理嵌套循环，但我们可以通过flatMap等方法展开流，
 * 然后用过滤器条件来找到符合条件的四元组。
 */
import java.util.stream.IntStream;

public class Solution {
    public int countIncreasingQuadruplets(int[] nums) {
        int n = nums.length;
        return (int) IntStream.range(0, n)
            .boxed()
            .flatMap(i -> IntStream.range(i + 1, n)
                .boxed()
                .flatMap(j -> IntStream.range(j + 1, n)
                    .boxed()
                    .flatMap(k -> IntStream.range(k + 1, n)
                        .filter(l -> nums[i] < nums[k] && nums[k] < nums[j] && nums[j] < nums[l])
                        .boxed()))
            ).count();
    }
}

题解采用了一种高效的方法来计算数组中的特定四元组的数量。整体思路是利用一个计数数组 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)