713.乘积小于K的子数组
713.乘积小于K的子数组
题解
题目:求乘积小于K的连续的子数组的个数
思路:
1.因为是连续的,所以可以用滑动窗口来做 2.如果当前这个数小于K,说明至少可以加1 3.如果乘积大于等于k,移动左指针,并缩小乘积 4.最后乘积必定小于k,那么ans+=right-left是什么意思呢? 5.[2,5,6],100 对于这种情况,答案有[6][2,5,6],[5,6] 6.其中[6]已经加过了,那么还剩两个,right-left=2
代码
func numSubarrayProductLessThanK(nums []int, k int) int { left, right := 0, 0 ans, cnt := 0, 1 for right < len(nums) { cnt *= nums[right] if nums[right] < k { ans++ } for cnt >= k && left < right { cnt /= nums[left] left++ } ans += right - left right++ } return ans }