1.题目
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
2.示例
示例 1：
输入：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 的子数组。
示例 2：
输入：nums = [1,2,3], k = 0
输出：0
提示:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
3.思路
开始想的是遍历数组，以数组的每一个数开头向后遍历。计算乘积，当乘积不小于k了，再从下一个数字开始向后开始新一轮的遍历。这样可以得到所有的子数组，写完发现题目只要子数组的数量，然后这个方法不出意外的超时了。
官方的代码看不太明白，就用双指针的思路写了第二个方法，只需要理解：右指针每位移到一个新位置，应该加上 right - left + 1 种数组组合就好了。
4.代码
暴力
func numSubarrayProductLessThanK(nums []int, k int) int { //暴力 var ans []int var product int for i, _ := range nums { if nums[i] < k { temp := []int{nums[i]} ans = append(ans,temp) product = nums[i] for j := i+1; j < len(nums); j++{ product = product*nums[j] if product < k { temp = append(temp, nums[j]) log.Println(temp,nums[j]) ans = append(ans, temp) log.Println(ans) }else { break } } } } return len(ans) }
双指针
func numSubarrayProductLessThanK(nums []int, k int) int { //数组中数的范围是1~1000,所以当k=0时,没有满足要求的数组 if k == 0 { return 0 } //记录区间内的乘积 product := 1 var ans,left,right int //使右指针移动到右端则结束 for right < len(nums) { //记录乘积 product *= nums[right] //当前区间内的乘积大于等于k，左指针右移并把之前左指针的数除掉 for product >= k { product /= nums[left] left++ } //每次右指针位移到一个新位置，应该加上 right - left + 1 种数组组合： // nums[right] // nums[right-1], nums[right] // nums[right-2], nums[right-1], nums[right] // nums[left], ......, nums[right-2], nums[right-1], nums[right] //共有 right - left + 1 种 ans += right - left + 1 //右指针右移 right++ } return ans }
