【力扣打卡系列】滑动窗口与双指针(乘积小于K的子数组)

坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day6

乘积小于K的子数组

• 题目描述
• 解题思路
  • 双指针移动，遍历右端点right，滑动左端点left
  • 子数组的个数：固定右端点r，子数组的个数其实就是从l到r的元素的个数，即r-l+1
  • 反向控制条件for sum >= k{}，当sum<k，即满足操作时，执行ans += right-left +1
• 代码参考

func numSubarrayProductLessThanK(nums []int, k int) int {left := 0sum := 1ans := 0if k <= 1 {return 0}for right,value :=range nums{sum *= valuefor sum >= k{sum /= nums[left]left++}ans += right-left +1}return ans
}

• tips
  • 双指针的应用场景
  • 指针移动的过程中，sum和是在不断变小的，while条件逐渐从满足要求变为不满足要求，这就是单调性，只有满足单调性才可以使用双指针
  • 子数组的个数：固定右端点r，子数组的个数其实就是从l到r的元素的个数，即r-l+1
  • 即[l,r]满足要求的话，[l,r],[l+1,r]…[r,r]都是满足要求的（固定右端点）