具有给定乘积的子阵列数-yiteyi-C++库

给定一个正数数组和一个数k，求出乘积正好等于k的子数组数。我们可以假设没有溢出。

null

例如：

Input : arr = [2, 1, 1, 1, 4, 5]        k = 4Output : 41st subarray : arr[1..4]2nd subarray : arr[2..4]3rd subarray : arr[3..4]4th subarray : arr[4]Input : arr = [1, 2, 3, 4, 1]        k = 24Output : 41st subarray : arr[0..4]2nd subarray : arr[1..4]3rd subarray : arr[1..3]4th subarray : arr[0..3]

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 是考虑所有子数组并找到它们的产品。对于每个产品，检查它是否等于k。如果是，则递增结果。

一 有效解决方案 就是使用滑动窗口技术可以用来解决这个问题。我们使用两个指针start和end来表示滑动窗口的起点和终点。最初，起点和终点都指向数组的起点，即索引0。继续递增结束，直到乘积p

为什么countOnes+1被添加到结果中？ 考虑上述样本案例中的第二个测试用例。如果我们遵循上述步骤，那么在递增end之后，我们将在start=0和end=3处到达。在此之后，countone设置为1。start=0有多少子阵列？有两个子阵列：arr[0..3]和arr[0..4]。观察子阵列[0..3]是我们使用滑动窗口技术发现的。这会将结果计数增加1，在表达式countOnes+1中表示为+1。另一个子阵列[0..4]只需将单个1添加到子阵列[0..3]即可获得，即一次添加1的个数。让我们试着概括一下。假设arr[0..i]是使用滑动窗口技术获得的子数组，让countOnes=j。然后我们可以通过向该子数组添加单个1，一次按单位长度扩展该子数组。在向arr[0..i]追加一个1后，新的子阵列为arr[0..i+1]，结果也增加了1。计数现在减少1，等于j–1。我们可以一次连续附加一个1，并获得一个新的子数组，直到countone不等于零。因此，结果计数按countone递增，并在表达式countone+1中表示为countone。因此，对于起始点的每一个增量，直到p等于k，只需在结果中加上countone+1即可。

请注意，上述算法不适用于k=1的情况。例如，考虑测试用例ARR[]= { 2, 1, 1，1 }。幸亏 杰尔·桑托基 对于这个测试用例。对于k=1的情况，我们将找到数组中所有元素都为1的每个段的长度。设1的特定段的长度为x。该段的子阵列数为x*（x+1）/2。所有这些子阵列都有乘积1，因为所有元素都是1。在给定的测试用例中，从索引1到索引3的1中只有一段长度为3。所以乘积为1的子阵列总数为（3*4）/2=6。

该算法可列为：

For k != 1:1. Initialize start = end = 02. Initialize res = 0, p = 1 3. Increment end until p < k4. When p = k do:     Set countOnes = number of succeeding ones     res += (countOnes+1)     Increment start until p = k     and do res += (countOnes+1)5. Stop if end = nFor k = 1:1. Find all segments in array in which    only 1 is present.2. Find length of each segment.3. Add length*(length+1) / 2 to result.

实施：

C++

                             // C++ program to find number of subarrays                           
                             // having product exactly equal to k.                           
                             #include <bits/stdc++.h>                           
                             using                                           namespace                                           std;                           
             
                             // Function to find number of subarrays                           
                             // having product equal to 1.                           
                             int                                           countOne(                                           int                                           arr[],                                           int                                           n){                           
                                                         int                                           i = 0;                           
                                         
                                                         // To store number of ones in                           
                                                         // current segment of all 1s.                           
                                                         int                                           len = 0;                           
                                         
                                                         // To store number of subarrays                           
                                                         // having product equal to 1.                           
                                                         int                                           ans = 0;                           
                                         
                                                         while                                           (i < n){                           
                                         
                                                         // If current element is 1, then                           
                                                         // find length of segment of 1s                           
                                                         // starting from current element.                           
                                                         if                                           (arr[i] == 1){                           
                                                         len = 0;                           
                                                         while                                           (i < n && arr[i] == 1){                           
                                                         i++;                           
                                                         len++;                           
                                                         }                           
                                         
                                                         // add number of possible                           
                                                         // subarrays of 1 to result.                           
                                                         ans += (len*(len+1)) / 2;                           
                                                         }                           
                                                         i++;                           
                                                         }                           
                                         
                                                         return                                           ans;                           
                             }                           
             
                             /// Function to find number of subarrays having                           
                             /// product exactly equal to k.                           
                             int                                           findSubarrayCount(                                           int                                           arr[],                                           int                                           n,                                           int                                           k)                           
                             {                           
                                                         int                                           start = 0, endval = 0, p = 1,                           
                                                         countOnes = 0, res = 0;                           
             
                                                         while                                           (endval < n)                           
                                                         {                           
                                                         p *= (arr[endval]);                           
             
                                                         // If product is greater than k then we need to decrease                           
                                                         // it. This could be done by shifting starting point of                           
                                                         // sliding window one place to right at a time and update                           
                                                         // product accordingly.                           
                                                         if                                           (p > k)                           
                                                         {                           
                                                         while                                           (start <= endval && p > k)                           
                                                         {                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
                                                         }                           
                                         
                                         
                                                         if                                           (p == k)                           
                                                         {                           
                                                         // Count number of succeeding ones.                           
                                                         countOnes = 0;                           
                                                         while                                           (endval + 1 < n && arr[endval + 1] == 1)                           
                                                         {                           
                                                         countOnes++;                           
                                                         endval++;                           
                                                         }                           
             
                                                         // Update result by adding both new subarray                           
                                                         // and effect of succeeding ones.                           
                                                         res += (countOnes + 1);                           
             
                                                         // Update sliding window and result according                           
                                                         // to change in sliding window. Here preceding                           
                                                         // 1s have same effect on subarray as succeeding                           
                                                         // 1s, so simply add.                           
                                                         while                                           (start <= endval && arr[start] == 1 && k!=1)                           
                                                         {                           
                                                         res += (countOnes + 1);                           
                                                         start++;                           
                                                         }                           
             
                                                         // Move start to correct position to find new                           
                                                         // subarray and update product accordingly.                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
             
                                                         endval++;                           
                                                         }                           
                                                         return                                           res;                           
                             }                           
             
                             // Driver code                           
                             int                                           main()                           
                             {                           
                                                         int                                           arr1[] = { 2, 1, 1, 1, 3, 1, 1, 4};                           
                                                         int                                           n1 =                                           sizeof                                           (arr1) /                                           sizeof                                           (arr1[0]);                           
                                                         int                                           k = 1;                           
                                         
                                                         if                                           (k != 1)                           
                                                         cout << findSubarrayCount(arr1, n1, k) <<                                           ""                                           ;                           
                                                         else                           
                                                         cout << countOne(arr1, n1) <<                                           ""                                           ;                           
                                         
                                                         int                                           arr2[] = { 2, 1, 1, 1, 4, 5};                           
                                                         int                                           n2 =                                           sizeof                                           (arr2) /                                           sizeof                                           (arr2[0]);                           
                                                         k = 4;                           
                                         
                                                         if                                           (k != 1)                           
                                                         cout << findSubarrayCount(arr2, n2, k) <<                                           ""                                           ;                           
                                                         else                           
                                                         cout << countOne(arr2, n2) <<                                           ""                                           ;                           
                                                         return                                           0;                           
                             }                           

JAVA

                             // Java program to find number of subarrays                           
                             // having product exactly equal to k.                           
                             import                                           java.util.*;                           
             
                             class                                           GFG                           
                             {                           
                                                         // Function to find number of subarrays having                           
                                                         // product exactly equal to k.                           
                                                         public                                           static                                           int                                           findSubarrayCount(                                           int                                           arr[],                                           int                                           n,                                           int                                           k)                           
                                                         {                           
                                                         int                                           start =                                           0                                           , endval =                                           0                                           ;                           
                                                         int                                           p =                                           1                                           , countOnes =                                           0                                           , res =                                           0                                           ;                           
                                                         while                                           (endval < n)                           
                                                         {                           
                                                         p *= (arr[endval]);                           
                                         
                                                         // If product is greater than k then we need                           
                                                         // to decrease it. This could be done by shifting                           
                                                         // starting point of sliding window one place                           
                                                         // to right at a time and update product accordingly.                           
                                                         if                                           (p > k)                           
                                                         {                           
                                                         while                                           (start <= endval && p > k)                           
                                                         {                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
                                                         }                           
                                         
                                                         if                                           (p == k)                           
                                                         {                           
                                                         // Count number of succeeding ones.                           
                                                         countOnes =                                           0                                           ;                           
                                                         while                                           (endval +                                           1                                           < n && arr[endval +                                           1                                           ] ==                                           1                                           )                           
                                                         {                           
                                                         countOnes++;                           
                                                         endval++;                           
                                                         }                           
                                         
                                                         // Update result by adding both new                           
                                                         // subarray and effect of succeeding ones.                           
                                                         res += (countOnes +                                           1                                           );                           
                                         
                                                         // Update sliding window and result according                           
                                                         // to change in sliding window. Here preceding                           
                                                         // 1s have same effect on subarray as succeeding                           
                                                         // 1s, so simply add.                           
                                                         while                                           (start <= endval && arr[start] ==                                           1                                           )                           
                                                         {                           
                                                         res += (countOnes +                                           1                                           );                           
                                                         start++;                           
                                                         }                           
                                         
                                                         // Move start to correct position to find new                           
                                                         // subarray and update product accordingly.                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
                                         
                                                         endval++;                           
                                                         }                           
                                                         return                                           res;                           
                                                         }                           
                                         
                                                         // Driver code                           
                                                         public                                           static                                           void                                           main (String[] args)                           
                                                         {                           
                                                         int                                           arr[] =                                           new                                           int                                           []{                                           2                                           ,                                           1                                           ,                                           1                                           ,                                           1                                           ,                                           4                                           ,                                           5                                           };                           
                                                         int                                           n = arr.length;                           
                                                         int                                           k =                                           4                                           ;                           
                                                         System.out.println(findSubarrayCount(arr, n, k));                           
                                                         }                           
                             }                           

Python3

                             # Python3 program to find number of subarrays                           
                             # having product exactly equal to k.                           
             
                             # Function to find number of subarrays                           
                             # having product equal to 1.                           
                             def                                           countOne(arr, n) :                           
                                                         i                                           =                                           0                           
                                         
                                                         # To store number of ones in                           
                                                         # current segment of all 1s.                           
                                                         Len                                           =                                           0                           
                                         
                                                         # To store number of subarrays                           
                                                         # having product equal to 1.                           
                                                         ans                                           =                                           0                           
                                         
                                                         while                                           (i < n) :                           
                                         
                                                         # If current element is 1, then                           
                                                         # find length of segment of 1s                           
                                                         # starting from current element.                           
                                                         if                                           (arr[i]                                           =                                           =                                           1                                           ) :                           
                                                         Len                                           =                                           0                           
                                                         while                                           (i < n                                           and                                           arr[i]                                           =                                           =                                           1                                           ) :                           
                                                         i                                           +                                           =                                           1                           
                                                         Len                                           +                                           =                                           1                           
                                         
                                                         # add number of possible                           
                                                         # subarrays of 1 to result.                           
                                                         ans                                           +                                           =                                           (                                           Len                                           *                                           (                                           Len                                           +                                           1                                           ))                                           /                                           /                                           2                           
                                                         i                                           +                                           =                                           1                           
                                         
                                                         return                                           ans                           
             
                             # Function to find number of subarrays having                           
                             # product exactly equal to k.                           
                             def                                           findSubarrayCount(arr, n, k) :                           
             
                                                         start, endval, p, countOnes, res                                           =                                           0                                           ,                                           0                                           ,                                           1                                           ,                                           0                                           ,                                           0                           
             
                                                         while                                           (endval < n) :                           
                                         
                                                         p                                           =                                           p                                           *                                           (arr[endval])                           
             
                                                         # If product is greater than k then we need to decrease                           
                                                         # it. This could be done by shifting starting point of                           
                                                         # sliding window one place to right at a time and update                           
                                                         # product accordingly.                           
                                                         if                                           (p > k) :                           
                                         
                                                         while                                           (start <                                           =                                           endval                                           and                                           p > k) :                           
                                         
                                                         p                                           =                                           p                                           /                                           /                                           arr[start]                           
                                                         start                                           +                                           =                                           1                           
                                         
                                                         if                                           (p                                           =                                           =                                           k) :                           
                                         
                                                         # Count number of succeeding ones.                           
                                                         countOnes                                           =                                           0                           
                                                         while                                           endval                                           +                                           1                                           < n                                           and                                           arr[endval                                           +                                           1                                           ]                                           =                                           =                                           1                                           :                           
                                         
                                                         countOnes                                           +                                           =                                           1                           
                                                         endval                                           +                                           =                                           1                           
             
                                                         # Update result by adding both new subarray                           
                                                         # and effect of succeeding ones.                           
                                                         res                                           +                                           =                                           (countOnes                                           +                                           1                                           )                           
             
                                                         # Update sliding window and result according                           
                                                         # to change in sliding window. Here preceding                           
                                                         # 1s have same effect on subarray as succeeding                           
                                                         # 1s, so simply add.                           
                                                         while                                           (start <                                           =                                           endval                                           and                                           arr[start]                                           =                                           =                                           1                                           and                                           k!                                           =                                           1                                           ) :                           
                                         
                                                         res                                           +                                           =                                           (countOnes                                           +                                           1                                           )                           
                                                         start                                           +                                           =                                           1                           
             
                                                         # Move start to correct position to find new                           
                                                         # subarray and update product accordingly.                           
                                                         p                                           =                                           p                                           /                                           /                                           arr[start]                           
                                                         start                                           +                                           =                                           1                           
             
                                                         endval                                           +                                           =                                           1                           
             
                                                         return                                           res                           
             
                             arr1                                           =                                           [                                           2                                           ,                                           1                                           ,                                           1                                           ,                                           1                                           ,                                           3                                           ,                                           1                                           ,                                           1                                           ,                                           4                                           ]                           
                             n1                                           =                                           len                                           (arr1)                           
                             k                                           =                                           1                           
             
                             if                                           (k !                                           =                                           1                                           ) :                           
                                                         print                                           (findSubarrayCount(arr1, n1, k))                           
                             else                                           :                           
                                                         print                                           (countOne(arr1, n1))                           
             
                             arr2                                           =                                           [                                           2                                           ,                                           1                                           ,                                           1                                           ,                                           1                                           ,                                           4                                           ,                                           5                                           ]                           
                             n2                                           =                                           len                                           (arr2)                           
                             k                                           =                                           4                           
             
                             if                                           (k !                                           =                                           1                                           ) :                           
                                                         print                                           (findSubarrayCount(arr2, n2, k))                           
                             else                                           :                           
                                                         print                                           (countOne(arr2, n2))                           
             
                                                         # This code is contributed by divyesh072019                           

C#

                             // C# program to find number                           
                             // of subarrays having product                           
                             // exactly equal to k.                           
                             using                                           System;                           
             
                             class                                           GFG                           
                             {                           
                                                         // Function to find number of                           
                                                         // subarrays having product                           
                                                         // exactly equal to k.                           
                                                         public                                           static                                           int                                           findSubarrayCount(                                           int                                           []arr,                           
                                                         int                                           n,                                           int                                           k)                           
                                                         {                           
                                                         int                                           start = 0, endval = 0;                           
                                                         int                                           p = 1, countOnes = 0, res = 0;                           
                                                         while                                           (endval < n)                           
                                                         {                           
                                                         p *= (arr[endval]);                           
                                         
                                                         // If product is greater than k                           
                                                         // then we need to decrease it.                           
                                                         // This could be done by shifting                           
                                                         // starting point of sliding window                           
                                                         // one place to right at a time and                           
                                                         // update product accordingly.                           
                                                         if                                           (p > k)                           
                                                         {                           
                                                         while                                           (start <= endval && p > k)                           
                                                         {                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
                                                         }                           
                                         
                                                         if                                           (p == k)                           
                                                         {                           
                                                         // Count number of                           
                                                         // succeeding ones.                           
                                                         countOnes = 0;                           
                                                         while                                           (endval + 1 < n &&                           
                                                         arr[endval + 1] == 1)                           
                                                         {                           
                                                         countOnes++;                           
                                                         endval++;                           
                                                         }                           
                                         
                                                         // Update result by adding                           
                                                         // both new subarray and                           
                                                         // effect of succeeding ones.                           
                                                         res += (countOnes + 1);                           
                                         
                                                         // Update sliding window and                           
                                                         // result according to change                           
                                                         // in sliding window. Here                           
                                                         // preceding 1s have same                           
                                                         // effect on subarray as                           
                                                         // succeeding 1s, so simply add.                           
                                                         while                                           (start <= endval &&                           
                                                         arr[start] == 1)                           
                                                         {                           
                                                         res += (countOnes + 1);                           
                                                         start++;                           
                                                         }                           
                                         
                                                         // Move start to correct position                           
                                                         // to find new subarray and update                           
                                                         // product accordingly.                           
                                                         p /= arr[start];                           
                                                         start++;                           
                                                         }                           
                                         
                                                         endval++;                           
                                                         }                           
                                                         return                                           res;                           
                                                         }                           
                                         
                                                         // Driver code                           
                                                         public                                           static                                           void                                           Main ()                           
                                                         {                           
                                                         int                                           []arr =                                           new                                           int                                           []{ 2, 1, 1,                           
                                                         1, 4, 5 };                           
                                                         int                                           n = arr.Length;                           
                                                         int                                           k = 4;                           
                                                         Console.WriteLine(findSubarrayCount(arr, n, k));                           
                                                         }                           
                             }                           
             
                             // This code is contributed by anuj_67.                           

PHP

                             <?php                           
                             // PHP program to find number of subarrays                           
                             // having product exactly equal to k.                           
             
                             // Function to find number of subarrays                           
                             // having product exactly equal to k.                           
                             function                                           findSubarrayCount(                                           $arr                                           ,                                           $n                                           ,                                           $k                                           )                           
                             {                           
                                                         $start                                           = 0;                           
                                                         $endval                                           = 0;                           
                                                         $p                                           = 1;                           
                                                         $countOnes                                           = 0;                           
                                                         $res                                           = 0;                           
             
                                                         while                                           (                                           $endval                                           <                                           $n                                           )                           
                                                         {                           
                                                         $p                                           *= (                                           $arr                                           [                                           $endval                                           ]);                           
             
                                                         // If product is greater than k                           
                                                         // then we need to decrease it.                           
                                                         // This could be done by shifting                           
                                                         // starting point of sliding window                           
                                                         // one place to right at a time and                           
                                                         // update product accordingly.                           
                                                         if                                           (                                           $p                                           >                                           $k                                           )                           
                                                         {                           
                                                         while                                           (                                           $start                                           <=                                           $endval                                           &&                                           $p                                           >                                           $k                                           )                           
                                                         {                           
                                                         $p                                           /=                                           $arr                                           [                                           $start                                           ];                           
                                                         $start                                           ++;                           
                                                         }                           
                                                         }                           
                                         
                                         
                                                         if                                           (                                           $p                                           ==                                           $k                                           )                           
                                                         {                           
                                         
                                                         // Count number of                           
                                                         // succeeding ones.                           
                                                         $countOnes                                           = 0;                           
                                                         while                                           (                                           $endval                                           + 1 <                                           $n                                           &&                           
                                                         $arr                                           [                                           $endval                                           + 1] == 1)                           
                                                         {                           
                                                         $countOnes                                           ++;                           
                                                         $endval                                           ++;                           
                                                         }                           
             
                                                         // Update result by adding                           
                                                         // both new subarray and                           
                                                         // effect of succeeding ones.                           
                                                         $res                                           += (                                           $countOnes                                           + 1);                           
             
                                                         // Update sliding window and                           
                                                         // result according to change                           
                                                         // in sliding window. Here                           
                                                         // preceding 1s have same                           
                                                         // effect on subarray as                           
                                                         // succeeding 1s, so simply                           
                                                         // add.                           
                                                         while                                           (                                           $start                                           <=                                           $endval                                           &&                           
                                                         $arr                                           [                                           $start                                           ] == 1)                           
                                                         {                           
                                                         $res                                           += (                                           $countOnes                                           + 1);                           
                                                         $start                                           ++;                           
                                                         }                           
             
                                                         // Move start to correct                           
                                                         // position to find new                           
                                                         // subarray and update                           
                                                         // product accordingly.                           
                                                         $p                                           /=                                           $arr                                           [                                           $start                                           ];                           
                                                         $start                                           ++;                           
                                                         }                           
             
                                                         $endval                                           ++;                           
                                                         }                           
                                                         return                                           $res                                           ;                           
                             }                           
             
                                                         // Driver Code                           
                                                         $arr                                           =                                           array                                           (2, 1, 1, 1, 4, 5);                           
                                                         $n                                           = sizeof(                                           $arr                                           ) ;                           
                                                         $k                                           = 4;                           
                                                         echo                                           findSubarrayCount(                                           $arr                                           ,                                           $n                                           ,                                           $k                                           );                           
                                         
                             // This code is contributed by aj_36                           
                             ?>                           

Javascript

                             <script>                           
             
                             // Javascript program to find number of subarrays                           
                             // having product exactly equal to k.                           
             
                             // Function to find number of subarrays                           
                             // having product equal to 1.                           
                             function                                           countOne(arr, n)                           
                             {                           
                                                         let i = 0;                           
             
                                                         // To store number of ones in                           
                                                         // current segment of all 1s.                           
                                                         let len = 0;                           
             
                                                         // To store number of subarrays                           
                                                         // having product equal to 1.                           
                                                         let ans = 0;                           
             
                                                         while                                           (i < n)                           
                                                         {                           
                                         
                                                         // If current element is 1, then                           
                                                         // find length of segment of 1s                           
                                                         // starting from current element.                           
                                                         if                                           (arr[i] == 1)                           
                                                         {                           
                                                         len = 0;                           
                                                         while                                           (i < n && arr[i] == 1)                           
                                                         {                           
                                                         i++;                           
                                                         len++;                           
                                                         }                           
             
                                                         // Add number of possible                           
                                                         // subarrays of 1 to result.                           
                                                         ans += parseInt((len * (len + 1)) / 2, 10);                           
                                                         }                           
                                                         i++;                           
                                                         }                           
                                                         return                                           ans;                           
                             }                           
             
                             /// Function to find number of subarrays having                           
                             /// product exactly equal to k.                           
                             function                                           findSubarrayCount(arr, n, k)                           
                             {                           
                                                         let start = 0, endval = 0, p = 1,                           
                                                         countOnes = 0, res = 0;                           
             
                                                         while                                           (endval < n)                           
                                                         {                           
                                                         p *= (arr[endval]);                           
             
                                                         // If product is greater than k then we                           
                                                         // need to decrease it. This could be                           
                                                         // done by shifting starting point of                           
                                                         // sliding window one place to right                           
                                                         // at a time and update product accordingly.                           
                                                         if                                           (p > k)                           
                                                         {                           
                                                         while                                           (start <= endval && p > k)                           
                                                         {                           
                                                         p = parseInt(p / arr[start], 10);                           
                                                         start++;                           
                                                         }                           
                                                         }                           
             
                                                         if                                           (p == k)                           
                                                         {                           
                                         
                                                         // Count number of succeeding ones.                           
                                                         countOnes = 0;                           
                                                         while                                           (endval + 1 < n && arr[endval + 1] == 1)                           
                                                         {                           
                                                         countOnes++;                           
                                                         endval++;                           
                                                         }                           
             
                                                         // Update result by adding both new subarray                           
                                                         // and effect of succeeding ones.                           
                                                         res += (countOnes + 1);                           
             
                                                         // Update sliding window and result according                           
                                                         // to change in sliding window. Here preceding                           
                                                         // 1s have same effect on subarray as succeeding                           
                                                         // 1s, so simply add.                           
                                                         while                                           (start <= endval &&                           
                                                         arr[start] == 1 && k != 1)                           
                                                         {                           
                                                         res += (countOnes + 1);                           
                                                         start++;                           
                                                         }                           
             
                                                         // Move start to correct position to find new                           
                                                         // subarray and update product accordingly.                           
                                                         p = parseInt(p / arr[start], 10);                           
                                                         start++;                           
                                                         }                           
                                                         endval++;                           
                                                         }                           
                                                         return                                           res;                           
                             }                           
             
                             // Driver code                           
                             let arr1 = [ 2, 1, 1, 1, 3, 1, 1, 4 ];                           
                             let n1 = arr1.length;                           
                             let k = 1;                           
                                         
                             if                                           (k != 1)                           
                                                         document.write(findSubarrayCount(arr1, n1, k) +                                           "</br>"                                           );                           
                             else                           
                                                         document.write(countOne(arr1, n1) +                                           "</br>"                                           );                           
                                         
                             let arr2 = [ 2, 1, 1, 1, 4, 5 ];                           
                             let n2 = arr2.length;                           
                             k = 4;                           
                                         
                             if                                           (k != 1)                           
                                                         document.write(findSubarrayCount(arr2, n2, k) +                                           "</br>"                                           );                           
                             else                           
                                                         document.write(countOne(arr2, n2) +                                           "</br>"                                           );                           
                                         
                             // This code is contributed by suresh07                           
             
                             </script>                           

输出：

时间复杂性： O（n） 辅助空间： O（1）

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

THE END

技术文章