滑动窗口算法中统计子数组元素数为何能得到符合条件的子数组总数

问题背景 #

给定正整数数组nums和整数k，返回乘积严格小于k的连续子数组的数量。
示例输入：nums = [10,5,2,6], k = 100
示例输出：8
符合条件的子数组为：[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

对应滑动窗口解法代码 #

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时，统计所有以right为结尾的、符合条件的连续子数组数量，累加所有右边界的计数即为总数量，不会出现重复或遗漏：任意一个符合条件的连续子数组都有且仅有一个唯一的右端点，只会被恰好统计一次。
当遍历到right时，我们通过移动左边界left，保证当前窗口[left, right]是以right为右端点的最长的、乘积严格小于k的连续子数组，此时符合条件的子数组数量刚好等于窗口长度right - left + 1：

• 任意取窗口内的索引i（left ≤ i ≤ right），子数组[i, right]的乘积一定小于k：因为窗口整体的乘积已经小于k，所有元素都是正整数，移除左边的元素只会让乘积更小，自然满足条件，这样的i一共有right - left + 1个。
• 所有窗口左边外的索引i < left对应的子数组[i, right]乘积一定≥k，已经通过移动左边界被排除，不需要统计。

示例过程验证 #

对应给出的示例遍历过程：

• right=0：窗口为[10]，以索引0结尾的符合条件子数组共1个：[10]，累加后总数为1
• right=1：窗口为[10,5]，以索引1结尾的符合条件子数组共2个：[5]、[10,5]，累加后总数为1+2=3
• right=2：乘积10*5*2=100不满足条件，移动左边界到1，窗口变为[5,2]，以索引2结尾的符合条件子数组共2个：[2]、[5,2]，累加后总数为3+2=5
• right=3：窗口为[5,2,6]，以索引3结尾的符合条件子数组共3个：[6]、[2,6]、[5,2,6]，累加后总数为5+3=8
  和示例输出结果完全一致。

内容的提问来源于stack exchange，提问作者souparno majumder