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 return2.
For each possible j and k (with j < k), count how many i < j have nums[i] < nums[k] and how many l > k have nums[j] < nums[l]. The answer is the sum over all (j, k) of the product of these two counts.
classSolution {
public:int countQuadruplets(vector<int>& nums) {
int n = nums.size(), ans =0;
for (int k =1; k < n -2; ++k) {
for (int j =0; j < k; ++j) {
if (nums[j] < nums[k]) {
int left =0, right =0;
for (int i =0; i < j; ++i) if (nums[i] < nums[k]) left++;
for (int l = k +1; l < n; ++l) if (nums[j] < nums[l]) right++;
ans += left * right;
}
}
}
return ans;
}
};
classSolution {
publicintcountQuadruplets(int[] nums) {
int n = nums.length, ans = 0;
for (int k = 1; k < n - 2; ++k) {
for (int j = 0; j < k; ++j) {
if (nums[j]< nums[k]) {
int left = 0, right = 0;
for (int i = 0; i < j; ++i) if (nums[i]< nums[k]) left++;
for (int l = k + 1; l < n; ++l) if (nums[j]< nums[l]) right++;
ans += left * right;
}
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funcountQuadruplets(nums: IntArray): Int {
val n = nums.size
var ans = 0for (k in1 until n-2) {
for (j in0 until k) {
if (nums[j] < nums[k]) {
var left = 0var right = 0for (i in0 until j) if (nums[i] < nums[k]) left++for (l in k+1 until n) if (nums[j] < nums[l]) right++ ans += left * right
}
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
defcountQuadruplets(self, nums: list[int]) -> int:
n, ans = len(nums), 0for k in range(1, n-2):
for j in range(0, k):
if nums[j] < nums[k]:
left = sum(1for i in range(j) if nums[i] < nums[k])
right = sum(1for l in range(k+1, n) if nums[j] < nums[l])
ans += left * right
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
pubfncount_quadruplets(nums: Vec<i32>) -> i32 {
let n = nums.len();
letmut ans =0;
for k in1..n-2 {
for j in0..k {
if nums[j] < nums[k] {
let left = (0..j).filter(|&i| nums[i] < nums[k]).count();
let right = (k+1..n).filter(|&l| nums[j] < nums[l]).count();
ans += left * right;
}
}
}
ans asi32 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
countQuadruplets(nums: number[]):number {
constn=nums.length;
letans=0;
for (letk=1; k<n-2; k++) {
for (letj=0; j<k; j++) {
if (nums[j] <nums[k]) {
letleft=0, right=0;
for (leti=0; i<j; i++) if (nums[i] <nums[k]) left++;
for (letl=k+1; l<n; l++) if (nums[j] <nums[l]) right++;
ans+=left*right;
}
}
}
returnans;
}
}