算法练习：乘积小于 K 的子数组（滑动窗口）

一.前言

今天奉上的题是来自LeetCode中的一道中等难度的题，但是如果了解滑动窗口的思想，其实这道题也是比较简单的，题目如下：

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于k 的连续子数组的数目。
示例一：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例二：

输入：nums = [1,2,3], k = 0
输出：0

二.思考

像这种从一个数组里面找一些子数组或者子字符串的问题大都可往这方面靠，一般来说都是可以解决的。因此我们大致思路是这样的，同样定义两个指针（一个叫left，一个叫i），它们都指向数组的第一个元素。我们用i指针来遍历数组，每当i指向新的元素时我们都计算i指针和left指针之间（窗口之间）元素的积并判断一下是否小于k，若成立则当前子数组就符合条件，用n来记录一次。反之，则i继续移动下去。

具体的我们看着代码来解释：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left = 0，i = 0;//定义左指针和右指针
        int n = 0;//用来记录子数组的个数
        int addtion = 1;//表示子数组中元素的积
        while(left < nums.length){//首先判断循环条件，当left指针指向nums的最后一个元素时，循环结束
            //循环进来后，计算i和left之间各元素的积
            addtion *= nums[i];
            i++;//i指针向后移动
            if (addtion >= k){//若子数组中的各元素积大于k
                left++;//说明子数组中元素超出条件范围，将left指针向右移动
                //让i重新和left指向同一元素，开始新一轮的查找，因此addtion也要归为原始状态
                i = left;
                addtion = 1;
            }else n++;//若符合条件，则记录一下，使n+1
            //但是还有一种情况，i到left之间的子数组都符合条件，这时i指向了数组的最后一个元素
            if (i == nums.length){
                //不能使i越界，因此将两个指针重新合到一块，重新开始新的查找，同理依然重置addtion
                i = left + 1;
                left++;
                addtion = 1;
            }
        }
        return n;//返回最后结果
    }
}

三.再次思考

如果理解了上面这个做法的话，那让我们想想是否还有更优解呢？
在上面这个做法中，我们每开始一次新的查找，都需要将i指针和left指针重新指向同一个新的元素，并且addtion也需要重置为1，这样看来这其中确实有不妥之处，那让我们来看看官方的的做法吧。
LeetCode官方题解：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length, ret = 0;
        int prod = 1, i = 0;//prod相当于我们之前的addtion
        for (int j = 0; j < n; j++) {
            prod *= nums[j];
            //官方给出的代码中以下和我们之前的方法有一点差异
            while (i <= j && prod >= k) {
                prod /= nums[i];
                i++;
            }
            ret += j - i + 1;//这是i和j指针之间的元素个数，它在数值上等于新增符合条件的子数组个数
        }
        return ret;
    }
}

思路与分析：整体思想和我们最开始讲的是一样的，只不过在记录子数组个数和重置各元素积这两部进行了优化。

我们着重讲述while中有差异的这段，我们可以这么理解：i指针相当于第一种方法的left，j指针相当于之前的i。这里while中有一个 i <= j 条件，这是用来控制i指针的范围的，也就是说i指针是不能超过j指针的，这样就会有一个好处：因为 j < n，所以i就不会超出数组的长度了，也就能避免我们第一种方法还要专门写个if来判断i是否越界，简化了代码。代码进入循环后，也就意味着 prod > k 了，这时我们为了符合条件，需要把i指针向后移动，而prod值只需要除以nums[i]就等于此时窗口中元素的值。这和我们第一种方法相比就显得非常优秀了，我们之前的方法需要每次把prod值归1，然后由要经历prod等于原来那个值的过程，这就显得有点多余了。