https://leetcode.cn/problems/count-increasing-quadruplets/description/

题目描述

给你一个长度为 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 是一个排列。

解题思路

只能想到暴力遍历
四层循环保证了 0 <= i < j < k < l < n
再判断 nums[i] < nums[k] < nums[j] < nums[l]

代码编写

public long countQuadruplets(int[] nums) {  
    // 四层循环保证了 0 <= i < j < k < l < n    long count = 0;  
    for (int i = 0; i < nums.length; i++) {  
        for (int j = i + 1; j < nums.length; j++) {  
            if (nums[i] >= nums[j]) {  
                continue;  
            }  
            for (int k = j + 1; k < nums.length; k++) {  
                if (nums[i] >= nums[k]) {  
                    continue;  
                }  
                if (nums[k] >= nums[j]) {  
                    continue;  
                }  
                for (int l = k + 1; l < nums.length; l++) {  
                    // 判断 nums[i] < nums[k] < nums[j] < nums[l]
                    if (nums[i] < nums[k] && nums[k] < nums[j] && nums[j] < nums[l]) {  
                        count++;  
                    }  
                }  
            }  
        }  
    }  
    return count;  
}

单元测试

  
System.out.println(new Solution2552().countQuadruplets(TransformUtils.intArrays("[1,3,2,4,5]")));  
System.out.println(new Solution2552().countQuadruplets(TransformUtils.intArrays("[1,2,3,4]")));    
// 超时了 答案：81701608  
System.out.println(new Solution2552().countQuadruplets(TransformUtils.intArrays(  
        "[211,201,290,127,218,235,335,10,41,384,317,157,138,239,347,1,87,190,12,80,161,410,249,136,181,182,442,314,365,228,3,105,51,445,214,358,258,144,368,176,42,156,88,27,25,429,316,370,24,293,79,319,425,120,199,253,395,159,143,287,99,393,292,269,344,439,68,282,377,19,14,371,375,266,28,310,325,169,115,379,248,340,184,158,223,131,348,50,280,198,112,155,318,222,367,163,59,70,399,90,189,281,267,452,134,313,312,209,170,434,356,187,132,330,203,423,33,54,246,305,299,333,121,128,202,419,196,119,331,178,449,77,141,162,294,309,386,140,109,200,149,29,89,35,306,403,242,108,185,251,279,424,255,291,261,392,250,125,373,212,303,341,400,233,114,188,268,195,217,240,58,260,73,215,137,254,160,91,433,332,167,101,151,397,431,207,123,311,374,11,83,225,65,289,208,338,204,413,85,78,4,148,352,360,402,426,154,93,361,94,21,322,36,146,96,44,350,219,166,229,364,349,75,31,451,378,359,139,142,63,372,102,307,171,221,263,231,273,252,383,346,369,437,116,145,67,404,43,210,180,339,66,422,414,243,130,271,420,276,238,191,227,62,454,118,324,435,110,302,244,47,8,97,382,37,129,2,111,389,49,48,432,357,284,366,436,113,81,165,381,175,427,343,327,13,15,5,186,329,173,53,106,295,197,336,133,380,448,232,16,60,391,441,315,220,415,256,245,362,126,55,326,296,320,213,52,323,71,297,421,152,440,206,401,272,407,270,446,277,387,30,57,23,177,76,168,301,39,298,385,22,417,34,122,174,390,259,95,274,32,64,82,194,216,98,394,334,17,278,247,321,264,92,20,74,72,26,9,443,286,409,236,376,183,411,262,135,205,193,428,38,308,396,18,117,234,107,398,328,345,354,363,416,104,103,56,61,164,86,237,100,257,46,192,418,40,453,337,351,283,7,355,342,304,406,45,300,285,6,179,447,226,265,408,450,230,275,288,412,430,438,69,147,444,224,84,124,388,172,353,405,241,150,153]")));

额外补充

// todo 用ai来分析思路