面试题9：乘积小于k的子数组（Java版）

题目：输入一个由正整数组成的数组和一个正整数k，请问数组
中有多少个数字乘积小于k的连续子数组？例如，输入数组[10，5，
2，6]，k的值为100，有8个子数组的所有数字的乘积小于100，它们
分别是[10]、[5]、[2]、[6]、[10，5]、[5，2]、[2，6]和[5，2，
6]。

// 因为是求连续子数组的个数所以可以使用左右指针的移动来确定满足条件的子数组个数
public static int numSubarrayProductLessThanK(int[] nums, int k) {
    long product = 1;
    int left = 0;
    int count = 0;
    for (int right = 0; right < nums.length; ++right) {
        product *= nums[right];
        while (left <= right && product >= k) {
            product /= nums[left++];
        }
        // 因为是连续子数组所以它们两个指针之间满足条件
        // 包含新增的那个右指针指向的数的子数组个数是
        // right - left + 1，（ps:因为不包含右指针的满足
        // 条件的子数组个数在之前已经加过了，所以就不重复加了）
        count += left <= right ? right - left + 1 : 0;
    }
    return count;
}