乘积小于 K 的子数组（滑动窗口）_滑动窗口解乘积小于 k 的子数组

简要分析，这个题目刚开始确实没想到滑动窗口，只是想到动态规划解法，时间复杂度为O（）,代码如下：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
         int n = nums.length;
         int ans = 0;
         for(int i = 0 ; i < n ; i++)
         {  
             int temp = nums[i];
             if(temp >= k)
              continue;
            else
               ans++;
             for(int j = 1 ; j < n -i ; j++)
             {   
                temp = temp * nums[i + j];
                 if(temp < k)
                   {
                       ans++;
                   }
                 else
                   break;
             }
         }
         return ans;
    }
}

简单提交后，效果有点惨：

 几乎是马上就要超时的状态。

滑动窗口的解法，因为数组内全部都是大于0的正数，所以随着窗口的扩大，乘积肯定是越来越大的状态，不满足条件时候便缩小窗口，这么一思考，代码的基本逻辑就。

缩小窗口的代码：用ans窗口区间的乘积

 while(i <= j && ans >= k)
             {
                 ans /= nums[i];
                 i++;
             }

 总体代码如下：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
         int n = nums.length , i = 0;
         int ans = 1;
         int count = 0;
 
         for(int j = 0 ; j < n ; j++)
         {
             ans *= nums[j];
             while(i <= j && ans >= k)
             {
                 ans /= nums[i];
                 i++;
             }
             count += (j - i + 1);
         }
         return count;
         
    }
}

时间复杂度只有O（n），