输入: 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的子数组。
本来想着从左往右延伸，但是当1特别多的时候，会时间过长，所以把注意力放在将多个1转换为1个1的做法了。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k < 2:
return 0
# 找出的个数
num = 0
# 把连续的多个1变成1个1
# 找出连续1的个数及转换后的位置
zero_nums = dict() # 连续1的个数，zero_nums[0]代表第1个连续1的个数
nums_t = []
zero_num = 0
for v in nums:
if v == 1:
zero_num += 1
else:
if zero_num>0:
zero_nums[len(nums_t)] = zero_num
zero_num = 0
nums_t.append(1)
nums_t.append(v)
if zero_num>0:
zero_nums[len(nums_t)] = zero_num
zero_num = 0
nums_t.append(1)
print(nums_t)
print(zero_nums)
# 乘
for i in range(len(nums_t)):
l = i
multi = 1
while True:
if l < len(nums_t):
multi *= nums_t[l]
else:
break
if multi < k:
# 如果首位为1
if nums_t[i] == 1:
if l == i:
# 开头为1
num += int(zero_nums[l]*int(zero_nums[l]+1)/2)
# print(zero_nums[l])
# print(num)
elif nums_t[l] == 1:
# 尾巴接着1
num += zero_nums[i] * zero_nums[l]
print(num)
else:
# 尾巴不接着1
num += zero_nums[i]
print(num)
else:
if nums_t[l] == 1:
# 尾巴接着1
num += zero_nums[l]
print(num)
else:
# 尾巴不接着1
num += 1
print(num)
l += 1
else:
break
return num
