具有给定乘积的子数组数
原文： https://www.geeksforgeeks.org/number-subarrays-given-product/
给定一个正数数组和一个数k，找到乘积恰好等于k的子数组数。 我们可以假设没有溢出。
示例：
Input : arr = [2, 1, 1, 1, 4, 5]
k = 4
Output : 4
1st 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 = 24
Output : 4
1st subarray : arr[0..4]
2nd subarray : arr[1..4]
3rd subarray : arr[1..3]
4th subarray : arr[0..3]
简单解决方案是考虑所有子数组并找到其乘积。 对于每个产品，检查它是否等于k。 如果是，则增加结果。
一种有效的解决方案是使用滑动窗口技术来解决该问题。 我们使用两个指针start和end来表示滑动窗口的起点和终点。
最初，起点和终点都指向数组的起点，即索引 0。保持终点递增，直到乘积p < k。 一旦p等于k，就停止end递增，并检查end的当前位置是否在数组中跟随一系列 1。 如果是，则那些 1 也将有助于子数组计数。 将这些后续 1 的计数存储在变量countOnes中。 此后，继续递增，直到p等于k，同时将结果加countOnes + 1。 如果开始与结束重合，则再次从增加结束处开始并遵循相同的步骤。 这样做直到end小于数组大小。
为什么将countOnes + 1添加到结果中？
在上述示例案例中，考虑第二个测试案例。 如果遵循上述过程，则在递增end之后，我们将到达start = 0且end = 3。此后，countOnes设置为 1。start = 0时有多少个子数组？ 有两个子数组：arr[0..3]和arr[0..4]。 观察到子数组[0..3]是我们使用滑动窗口技术发现的。 这将结果计数增加 1，并由表达式countOnes + 1中的 +1 表示。通过将单个 1 附加到子数组[0..3]，即添加countOnes数，即可轻松获得另一个subarray[0..4]。 一次 1s。 让我们尝试概括一下。 假设arr[0..i]是使用滑动窗口技术获得的子数组，并且让countOnes = j。 然后，通过将单个 1 附加到此子数组，可以一次按单位长度扩展此子数组。 在将单个 1 附加到arr[0..i]之后，新的子数组为arr[0..i + 1]，结果也增加 1。countOnes现在减小 1 等于j – 1。我们可以连续一次附加单个 1，并获得一个新的子数组，直到countOnes不等于零为止。
因此，结果计数增加countOnes，并在表达式countOnes + 1中表示为countOnes。因此，对于开始的每个增量，直到p等于k为止，只需在结果中加上countOnes + 1。
注意，当k = 1时，上述算法将不起作用。 考虑测试用例arr[] = {2, 1, 1, 1}。 感谢 Jeel Santoki 的这个测试案例。 对于k = 1的情况，我们将找到其中所有元素均为 1 的数组每个段的长度。令 1 的特定段的长度为x。 该段的子数组数将为x * (x + 1) / 2。 所有这些子数组都将具有乘积 1，因为所有元素都是 1。在给定的测试用例中，从索引 1 到索引 3 的长度只有 3 的 1 个分段，因此乘积 1 的子数组总数为(3 * 4) / 2 = 6。
该算法可以列为：
For k != 1:
1\. Initialize start = end = 0
2\. Initialize res = 0, p = 1
3\. Increment end until p < k
4\. 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 = n
For 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) << "\n";
else
cout << countOne(arr1, n1) << "\n";
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) << "\n";
else
cout << countOne(arr2, n2) << "\n";
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));
}
}
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
?>
输出：
9
4
时间复杂度：O(n)。
辅助空间：O(1)。
版权属于：月萌API www.moonapi.com，转载请注明出处
