最小值和最大值相同的子阵列数-yiteyi-C++库

给定一个由n个整数组成的数组，找出最小和最大元素相同的子数组的数目。子数组定义为连续元素的非空序列。

null

例如：

Input: 2 3 1 1 Output: 5Explanation: The subarrays are (2), (3), (1), (1) and (1, 1) Input: 2 4 5 3 3 3Output: 9Explanation: The subarrays are (2), (4), (5), (3), (3, 3), (3, 3, 3), (3), (3, 3) and (3)

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

首先要注意的是，只有那些所有元素都相同的子阵列才会具有相同的最小值和最大值。不同的元素显然意味着不同的最小值和最大值。因此，我们只需要计算连续相同元素的数量 （说d） ，然后通过组合公式，我们得到子阵的数量为——

d元素=（d*（d+1）/2）可能的子阵列数量其中d是连续的相同元素的数量。

我们从1-n遍历，然后从I+1遍历到n，然后找到连续相同元素的数量，然后将不可能的子数组添加到结果中。

C++

                         // CPP program to count number of subarrays                       
                         // having same minimum and maximum.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // calculate the no of contiguous subarrays                       
                         // which has same minimum and maximum                       
                         int                                     calculate(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 // stores the answer                       
                                                 int                                     ans = 0;                       
           
                                                 // loop to traverse from 0-n                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // start checking subarray from next element                       
                                                 int                                     r = i + 1;                       
           
                                                 // traverse for finding subarrays                       
                                                 for                                     (                                     int                                     j = r; j < n; j++) {                       
           
                                                 // if the elements are same then                       
                                                 // we check further and keep a count                       
                                                 // of same numbers in 'r'                       
                                                 if                                     (a[i] == a[j])                       
                                                 r += 1;                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // the no of elements in between r and i                       
                                                 // with same elements.                       
                                                 int                                     d = r - i;                       
           
                                                 // the no of subarrays that can be formed                       
                                                 // between i and r                       
                                                 ans += (d * (d + 1) / 2);                       
           
                                                 // again start checking from the next index                       
                                                 i = r - 1;                       
                                                 }                       
           
                                                 // returns answer                       
                                                 return                                     ans;                       
                         }                       
           
                         // drive program to test the above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { 2, 4, 5, 3, 3, 3 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 cout << calculate(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number of subarrays                       
                         // having same minimum and maximum.                       
           
                         class                                     Subarray                       
                         {                       
                                                 // calculate the no of contiguous subarrays                       
                                                 // which has same minimum and maximum                       
                                                 static                                     int                                     calculate(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 // stores the answer                       
                                                 int                                     ans =                                     0                                     ;                       
           
                                                 // loop to traverse from 0-n                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // start checking subarray from                       
                                                 // next element                       
                                                 int                                     r = i +                                     1                                     ;                       
           
                                                 // traverse for finding subarrays                       
                                                 for                                     (                                     int                                     j = r; j < n; j++) {                       
           
                                                 // if the elements are same then                       
                                                 // we check further and keep a                       
                                                 // count of same numbers in 'r'                       
                                                 if                                     (a[i] == a[j])                       
                                                 r +=                                     1                                     ;                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // the no of elements in between r                       
                                                 // and i with same elements.                       
                                                 int                                     d = r - i;                       
           
                                                 // the no. of subarrays that can be                       
                                                 // formed between i and r                       
                                                 ans += (d * (d +                                     1                                     ) /                                     2                                     );                       
           
                                                 // again start checking from the next                       
                                                 // index                       
                                                 i = r -                                     1                                     ;                       
                                                 }                       
           
                                                 // returns answer                       
                                                 return                                     ans;                       
                                                 }                       
                                   
                                                 // Driver program to test above functions                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     a[] = {                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     3                                     ,                                     3                                     ,                                     3                                     };                       
                                                 System.out.println(calculate(a, a.length));                       
                                                 }                       
                         }                       
                         // This code is contributed by Prerna Saini                       

Python3

                         # Python3 program to count                       
                         # number of subarrays having                       
                         # same minimum and maximum.                       
           
                         # calculate the no of contiguous                       
                         # subarrays which has same                       
                         # minimum and maximum                       
                         def                                     calculate(a, n):                       
                                   
                                                 # stores the answer                       
                                                 ans                                     =                                     0                                     ;                       
                                                 i                                     =                                     0                                     ;                       
           
                                                 # loop to traverse from 0-n                       
                                                 while                                     (i < n):                       
                                   
                                                 # start checking subarray                       
                                                 # from next element                       
                                                 r                                     =                                     i                                     +                                     1                                     ;                       
           
                                                 # traverse for                       
                                                 # finding subarrays                       
                                                 for                                     j                                     in                                     range                                     (r, n):                       
                                   
                                                 # if the elements are same                       
                                                 # then we check further                       
                                                 # and keep a count of same                       
                                                 # numbers in 'r'                       
                                                 if                                     (a[i]                                     =                                     =                                     a[j]):                       
                                                 r                                     =                                     r                                     +                                     1                                     ;                       
                                                 else                                     :                       
                                                 break                                     ;                       
           
                                                 # the no of elements in                       
                                                 # between r and i with                       
                                                 # same elements.                       
                                                 d                                     =                                     r                                     -                                     i;                       
           
                                                 # the no of subarrays that                       
                                                 # can be formed between i and r                       
                                                 ans                                     =                                     ans                                     +                                     (d                                     *                                     (d                                     +                                     1                                     )                                     /                                     2                                     );                       
           
                                                 # again start checking                       
                                                 # from the next index                       
                                                 i                                     =                                     r                                     -                                     1                                     ;                       
                                                 i                                     =                                     i                                     +                                     1                                     ;                       
           
                                                 # returns answer                       
                                                 return                                     int                                     (ans);                       
           
                         # Driver Code                       
                         a                                     =                                     [                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     3                                     ,                                     3                                     ,                                     3                                     ];                       
                         n                                     =                                     len                                     (a);                       
                         print                                     (calculate(a, n));                       
           
                         # This code is contributed by mits                       

C#

                         // Program to count number                       
                         // of subarrays having same                       
                         // minimum and maximum.                       
                         using                                     System;                       
           
                         class                                     Subarray {                       
                                                 // calculate the no of contiguous                       
                                                 // subarrays which has the same                       
                                                 // minimum and maximum                       
                                                 static                                     int                                     calculate(                                     int                                     [] a,                                     int                                     n)                       
                                                 {                       
                                                 // stores the answer                       
                                                 int                                     ans = 0;                       
           
                                                 // loop to traverse from 0-n                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // start checking subarray                       
                                                 // from next element                       
                                                 int                                     r = i + 1;                       
           
                                                 // traverse for finding subarrays                       
                                                 for                                     (                                     int                                     j = r; j < n; j++) {                       
           
                                                 // if the elements are same then                       
                                                 // we check further and keep a                       
                                                 // count of same numbers in 'r'                       
                                                 if                                     (a[i] == a[j])                       
                                                 r += 1;                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // the no of elements in between                       
                                                 // r and i with same elements.                       
                                                 int                                     d = r - i;                       
           
                                                 // the no. of subarrays that can                       
                                                 // be formed between i and r                       
                                                 ans += (d * (d + 1) / 2);                       
           
                                                 // again start checking from                       
                                                 // the next index                       
                                                 i = r - 1;                       
                                                 }                       
           
                                                 // returns answer                       
                                                 return                                     ans;                       
                                                 }                       
           
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] a = { 2, 4, 5, 3, 3, 3 };                       
                                                 Console.WriteLine(calculate(a, a.Length));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

PHP

                         <?php                       
                         // PHP program to count number                       
                         // of subarrays having same                       
                         // minimum and maximum.                       
           
                         // calculate the no of contiguous                       
                         // subarrays which has same minimum                       
                         // and maximum                       
                         function                                     calculate(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 // stores the answer                       
                                                 $ans                                     = 0;                       
           
                                                 // loop to traverse from 0-n                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // start checking subarray                       
                                                 // from next element                       
                                                 $r                                     =                                     $i                                     + 1;                       
           
                                                 // traverse for finding subarrays                       
                                                 for                                     (                                     $j                                     =                                     $r                                     ;                                     $j                                     <                                     $n                                     ;                                     $j                                     ++)                       
                                                 {                       
           
                                                 // if the elements are same                       
                                                 // then we check further and                       
                                                 // keep a count of same numbers                       
                                                 // in 'r'                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] ==                                     $a                                     [                                     $j                                     ])                       
                                                 $r                                     += 1;                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // the no of elements in between                       
                                                 //  r and i with same elements.                       
                                                 $d                                     =                                     $r                                     -                                     $i                                     ;                       
           
                                                 // the no of subarrays that                       
                                                 // can be formed between i and r                       
                                                 $ans                                     += (                                     $d                                     * (                                     $d                                     + 1) / 2);                       
           
                                                 // again start checking                       
                                                 // from the next index                       
                                                 $i                                     =                                     $r                                     - 1;                       
                                                 }                       
           
                                                 // returns answer                       
                                                 return                                     $ans                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $a                                     =                                     array                                     ( 2, 4, 5, 3, 3, 3 );                       
                         $n                                     =                                     count                                     (                                     $a                                     );                       
                         echo                                     calculate(                                     $a                                     ,                                     $n                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
                         // JavaScript program to count number of subarrays                       
                         // having same minimum and maximum.                       
           
           
                                                 // calculate the no of contiguous subarrays                       
                                                 // which has same minimum and maximum                       
                                                 function                                     calculate(a, n)                       
                                                 {                       
                                                 // stores the answer                       
                                                 let ans = 0;                       
           
                                                 // loop to traverse from 0-n                       
                                                 for                                     (let i = 0; i < n; i++) {                       
           
                                                 // start checking subarray from                       
                                                 // next element                       
                                                 let r = i + 1;                       
           
                                                 // traverse for finding subarrays                       
                                                 for                                     (let j = r; j < n; j++) {                       
           
                                                 // if the elements are same then                       
                                                 // we check further and keep a                       
                                                 // count of same numbers in 'r'                       
                                                 if                                     (a[i] == a[j])                       
                                                 r += 1;                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // the no of elements in between r                       
                                                 // and i with same elements.                       
                                                 let d = r - i;                       
           
                                                 // the no. of subarrays that can be                       
                                                 // formed between i and r                       
                                                 ans += (d * (d + 1) / 2);                       
           
                                                 // again start checking from the next                       
                                                 // index                       
                                                 i = r - 1;                       
                                                 }                       
           
                                                 // returns answer                       
                                                 return                                     ans;                       
                                                 }                       
           
                         // Driver Code                       
           
                                                 let a = [ 2, 4, 5, 3, 3, 3 ];                       
                                                 document.write(calculate(a, a.length));                       
                                   
                         </script>                       

输出：

时间复杂性： O（n^2） 辅助空间： O（1）本文由 拉贾·维克拉马蒂亚（Raj） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章