一.前言
本日奉上的题是来自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指针向后移动 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++; } 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就便是此时窗口中元素的值。这和我们第一种方法相比就显得非常良好了，我们之前的方法须要每次把prod值归1，然后由要经历prod便是原来谁人值的过程，这就显得有点多余了。 |
