如何计算子数组中的元素给出滑动 window 算法中子数组的数量

Question

考虑以下问题:-

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.

使用滑动window方法解决这个问题是：-

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的子数组总数？

Answer 1

你首先要搞清楚for循环的不变量是什么。在 for 循环的每次迭代中，它固定一个 right，并找到最左边的 left，使得范围 [left, right] 包含乘积最接近但不超过 100 的元素，对于该特定right.

的值

例如，在上一次迭代中，找到的范围是[1, 3]，具有该范围的子数组是[5, 2, 6]。请注意，如果我们从左侧再包含一个元素，则乘积将等于或超过 100。您可以将其视为找到最长以 right 结尾的子数组产品小于 100。

假设整数都是正数，那么如果我们知道以 right 结尾的最长子数组满足这个条件，我们也知道任何更短的子数组以 right 结尾right也会满足这个条件。恰好有 (right - left) 个比我们发现的最长子数组更短的子数组。因此，每次我们找到一个 left，我们计算 (right - left)，再加上我们找到的最长的一个。这将是满足条件的以 right 结尾的子数组的总数。

由于for循环检查子数组的每个可能的结束位置（right），并且我们计算了每个结束位置满足条件的所有子数组，我们计算了所有子数组满足条件。

如何计算子数组中的元素给出滑动 window 算法中子数组的数量

How is counting the elements in the subarray giving the number of subarrays in the sliding window algorithm

java

algorithm

sliding-window