大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

找出整数数组 nums 中，所有乘积小于 k的「连续子数组」。

注意，「子数组」是连续的，而「子序列」可以不连续。

解题方法

滑动窗口

本题关键点：

  • 是求「子数组」，是连续的；
  • 数组中所有数字均为正数；
  • 只求个数，不用求出所有的结果。

上面的这三条，正是使用「滑动窗口」来解决的完美条件。

可以使用我多次分享的滑动窗口模板解决，模板在代码之后。

本题的滑动窗口定义：所有元素的乘积严格小于 713. 乘积小于 K 的子数组 - 图1 的连续子数组。

具体的做法：
1. 使用 713. 乘积小于 K 的子数组 - 图2 和 713. 乘积小于 K 的子数组 - 图3两个指针，分别指向滑动窗口的左右边界。

  1. 求窗口内所有的乘积，并判断：
    1. 713. 乘积小于 K 的子数组 - 图4 主动右移：713. 乘积小于 K 的子数组 - 图5 指针每次移动一步：每次移动右指针之后，符合题目要求的结果增加的是此窗口内的子数组数量，也就是 713. 乘积小于 K 的子数组 - 图6；
    2. 713. 乘积小于 K 的子数组 - 图7被动右移：如果乘积大于等于 713. 乘积小于 K 的子数组 - 图8了，需要移动左指针。

可以完全套用本文的滑动窗口模板，根本不用思考。

  1. class Solution(object):
  2.     def numSubarrayProductLessThanK(self, nums, k):
  3.         N = len(nums) # 数组/字符串长度
  4.         left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
  5.         prods = 1 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
  6.         res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
  7.         while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
  8.             prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数
  9.             while prods >= k and left <= right: # 此时需要一直移动左指针，直至找到一个符合题意的区间
  10.                 prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
  11.                 left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
  12.             # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
  13.             res += right - left + 1 # 需要更新结果
  14.             right += 1 # 移动右指针，去探索新的区间
  15.         return res

复杂度

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

分享滑动窗口模板

《挑战程序设计竞赛》这本书中把滑动窗口叫做「尺取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

  1. def findSubArray(nums):
  2.     N = len(nums) # 数组/字符串长度
  3.     left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
  4.     sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
  5.     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
  6.     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
  7.         sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
  8.         while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
  9.             sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
  10.             left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
  11.         # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
  12.         res = max(res, right - left + 1) # 需要更新结果
  13.         right += 1 # 移动右指针，去探索新的区间
  14.     return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

  1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
  2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；
  3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
  4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
  5. right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 713. 乘积小于 K 的子数组 - 图9 不符合题意 。

对于本题而言，就是该区间内的元素的乘积 大于等于了 713. 乘积小于 K 的子数组 - 图10 。

总结

  1. 本文的证明非常、非常详细，实际不难，有些笔试题中可能会考这个代码。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。