考慮以下問題：-
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.
例子：
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
使用滑動視窗方法對此的解決方案是：-
public class Main {
public static void main(String[] args) {
int arr[] = {10, 5,2, 6};
int k = 100;
int prod = 1, ans = 0, left = 0;
for (int right = 0; right < arr.length; right ) {
prod *= arr[right];
while (prod >= k) prod /= arr[left ];
ans = right - left 1;
}
System.out.println(ans);
}
}
這是我的問題：-right - left -1給出提取的子陣列中的元素總數，那么這如何正確計算子陣列
的總數？
即：對于一個陣列 [10, 5, 2, 6]
right=0; left=0; (right-left 1)=1; list=[10]
right=1; left=0; (right-left 1)=2; list=[10, 5]
right=2; left=1; (right-left 1)=2; list=[5, 2]
right=3; left=1; (right-left 1)=3; list=[5, 2, 6]
在遍歷陣列時計算子陣列中元素數量的邏輯是什么，將獲得乘積小于 K 的可能子陣列總數？
uj5u.com熱心網友回復：
您應該首先弄清楚 for 回圈的不變數是什么。在 for 回圈的每次迭代中，它修復 a right，并找到最左邊的left，使得范圍 [left, right] 包含乘積最接近但不超過 100 的元素，對于 的特定值right。
例如，在上次迭代中，找到的范圍是 [1, 3]，具有該范圍的子陣列是 [5, 2, 6]。請注意，如果我們從左側再包含一個元素，則乘積將等于或超過 100。您可以將其視為找到以乘積小于 100結尾的最長子陣列right。
假設整數都是正數，那么如果我們知道以結尾的最長子陣列right滿足這個條件，我們也知道任何以 結尾的較短子陣列right也滿足這個條件。有(right - left)比我們發現的最長的更短的子陣列。因此，每次我們找到 a 時left，我們都會計算(right - left)，加上我們找到的最長的一個。這將是right滿足條件的子陣列的總數。
由于for回圈檢查right子陣列的每個可能的結束位置 ( )，并且我們計算了每個結束位置滿足條件的所有子陣列，因此我們計算了所有滿足條件的子陣列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313532.html