具有給定乘積的子數組數 · 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; } ```