题目描述

给定一个由 n 个正整数组成的数组 nums，并给出一个正整数 s，请找出数组中元素乘积大于等于 s 的最短连续子数组的长度并输出；若不存在满足条件的子数组，输出 0。

输入格式

共 3 行：

1. 第 1 行：整数 n（数组长度）

2. 第 2 行：n 个用空格分隔的正整数（数组元素）

3. 第 3 行：整数 s（目标乘积）

输出格式

共 1 行：满足条件的最短连续子数组长度；若无解则输出 0。

样例输入

10
1 2 4 6 3 7 1 2 8 7
9

样例输出

2

样例解释

数组中乘积 ≥9 的最短连续子数组有：

• [2,4]（乘积=8，不满足）

• [4,6]（乘积=24≥9，长度2）

• [3,7]（乘积=21≥9，长度2）

• [2,8]（乘积=16≥9，长度2）

因此最短长度为 2。

数据规模与约定

最短子串积讲解视频

基础约束（100% 数据）

• 数组长度：1 ≤ n ≤ 10^4（修正原下限5，覆盖单元素、小数据边界场景）

• 数组元素：1 ≤ nums[i] ≤ 10^6（正整数，保证乘积随窗口扩大单调递增）

• 1 ≤ s ≤ 10^18 （注意s为1的情况）

算法保障约束

• 输入数据保证：滑动窗口算法运行过程中，所有有效窗口内的元素乘积均不超过 10^18，可直接使用long long完成计算，无需编写高精度代码。

解题提示

由于数组内所有元素均为正整数，窗口向右扩大时乘积只会递增不会递减，适合用滑动窗口（毛毛虫法）求解，时间复杂度为O(n)。代码编写时注意：必须用64位整数类型存储乘积，防止数据溢出。