乘积小于 K 的子数组

记住「右扩乘、超了就左缩除、每步加 right−left+1」,下面每一格都在套它。

这一行是数组,全是正整数。窗口从空开始、乘积 prod=1,右指针从左往右一格格扩,我们盯着 prod 和 ans 怎么变。

右指针到第 0 位(值 10),乘进窗口,乘积变成 10。仍然 < k=100,窗口合法。

窗口 [0, 0] 合法。以第 0 位结尾、左端从 0 到 0 的子数组乘积都 < 100,共 1 个,答案加 1,累计 1。

右指针到第 1 位(值 5),乘进窗口,乘积变成 50。仍然 < k=100,窗口合法。

窗口 [0, 1] 合法。以第 1 位结尾、左端从 0 到 1 的子数组乘积都 < 100,共 2 个,答案加 2,累计 3。

右指针到第 2 位(值 2),乘进窗口,乘积变成 100。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。

把左指针右移 1 步、依次除掉移出位,乘积回到 10(<100)。现在窗口是 [1, 2],以第 2 位结尾的合法子数组有 2 个(左端可取 1 到 2),答案加 2,累计 5。

右指针到第 3 位(值 6),乘进窗口,乘积变成 60。仍然 < k=100,窗口合法。

窗口 [1, 3] 合法。以第 3 位结尾、左端从 1 到 3 的子数组乘积都 < 100,共 3 个,答案加 3,累计 8。

右指针到第 4 位(值 1),乘进窗口,乘积变成 60。仍然 < k=100,窗口合法。

窗口 [1, 4] 合法。以第 4 位结尾、左端从 1 到 4 的子数组乘积都 < 100,共 4 个,答案加 4,累计 12。

右指针到第 5 位(值 8),乘进窗口,乘积变成 480。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。

把左指针右移 1 步、依次除掉移出位,乘积回到 96(<100)。现在窗口是 [2, 5],以第 5 位结尾的合法子数组有 4 个(左端可取 2 到 5),答案加 4,累计 16。

右指针到第 6 位(值 3),乘进窗口,乘积变成 288。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。

把左指针右移 2 步、依次除掉移出位,乘积回到 24(<100)。现在窗口是 [4, 6],以第 6 位结尾的合法子数组有 3 个(左端可取 4 到 6),答案加 3,累计 19。

右指针到第 7 位(值 2),乘进窗口,乘积变成 48。仍然 < k=100,窗口合法。

窗口 [4, 7] 合法。以第 7 位结尾、左端从 4 到 7 的子数组乘积都 < 100,共 4 个,答案加 4,累计 23。

右指针到第 8 位(值 4),乘进窗口,乘积变成 192。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。

把左指针右移 2 步、依次除掉移出位,乘积回到 24(<100)。现在窗口是 [6, 8],以第 8 位结尾的合法子数组有 3 个(左端可取 6 到 8),答案加 3,累计 26。

右指针到第 9 位(值 7),乘进窗口,乘积变成 168。它 ≥ k=100(红),窗口里乘积太大,下一步要左缩。

把左指针右移 1 步、依次除掉移出位,乘积回到 56(<100)。现在窗口是 [7, 9],以第 9 位结尾的合法子数组有 3 个(左端可取 7 到 9),答案加 3,累计 29。

扫完全程,把每个右端点贡献的「right−left+1」加起来,一共 29 个乘积小于 100 的子数组。右、左指针各只走一遍,O(n)。

边界先想清:k≤1 返回 0、全合法时是所有子数组数、单元素看它本身。

面试常考:用「以 right 结尾」论证不重不漏,以及正整数这个前提为何关键。