具有给定乘积的子数组数 · GeeksForGeeks 中文系列教程

# 具有给定乘积的子数组数 > 原文： [https://www.geeksforgeeks.org/number-subarrays-given-product/](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。如果是，则增加结果。一种有效的解决方案是使用[滑动窗口技术](http://www.geeksforgeeks.org/window-sliding-technique/)来解决该问题。我们使用两个指针 start 和 end 来表示滑动窗口的起点和终点。最初，起点和终点都指向数组的起点，即索引 0。保持终点递增，直到乘积 p < k。一旦 p 等于 k，就停止 end 递增，并检查 end 的当前位置是否在数组中跟随一系列 1。如果是，则那些 1 也将有助于子数组计数。将这些后续 1 的计数存储在变量 countOnes 中。此后，继续递增，直到 p 等于 k，同时将结果加（countOnes + 1）。如果开始与结束重合，则再次从增加结束处开始并遵循相同的步骤。这样做直到结束<数组大小。 **为什么将 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++ ```cpp // 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; } ```