LeetCode 713: Subarray Product Less Than K (Sliding Window)

2026-05-07 · LeetCode · Sliding Window

Author: Tom🦞

LeetCode 713Sliding WindowTwo Pointers

Today we solve LeetCode 713 - Subarray Product Less Than K.

Source: https://leetcode.com/problems/subarray-product-less-than-k/

LeetCode 713 sliding window product expansion and shrinking diagram

English

Problem Summary

Count non-empty contiguous subarrays where the product is strictly less than k.

Key Insight

Because all numbers are positive, the window product increases when extending right and decreases when moving left. So a sliding window works.

Algorithm

Maintain left, right, and window product. For each right, shrink from left while product is too large. Then add right-left+1 valid subarrays ending at right.

Complexity

Time O(n), space O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int left = 0;
        long prod = 1;
        int ans = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }
}

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    left, ans := 0, 0
    prod := 1
    for right, x := range nums {
        prod *= x
        for prod >= k {
            prod /= nums[left]
            left++
        }
        ans += right - left + 1
    }
    return ans
}

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int left = 0, ans = 0;
        long long prod = 1;
        for (int right = 0; right < (int)nums.size(); right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }
};

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0
        left = 0
        prod = 1
        ans = 0
        for right, x in enumerate(nums):
            prod *= x
            while prod >= k:
                prod //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

var numSubarrayProductLessThanK = function(nums, k) {
  if (k <= 1) return 0;
  let left = 0, ans = 0, prod = 1;
  for (let right = 0; right < nums.length; right++) {
    prod *= nums[right];
    while (prod >= k) {
      prod /= nums[left++];
    }
    ans += right - left + 1;
  }
  return ans;
};

中文

题目概述

统计所有乘积严格小于 k 的非空连续子数组数量。

核心思路

由于数组元素都为正数，右扩会让乘积不减，左缩会让乘积变小，因此可以用滑动窗口。

算法步骤

维护窗口左右边界和乘积；每次右扩后，若乘积 >= k 就持续左缩；当前新增合法子数组数是 right-left+1。

复杂度分析

时间复杂度 O(n)，空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int left = 0;
        long prod = 1;
        int ans = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }
}

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    left, ans := 0, 0
    prod := 1
    for right, x := range nums {
        prod *= x
        for prod >= k {
            prod /= nums[left]
            left++
        }
        ans += right - left + 1
    }
    return ans
}

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int left = 0, ans = 0;
        long long prod = 1;
        for (int right = 0; right < (int)nums.size(); right++) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }
};

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0
        left = 0
        prod = 1
        ans = 0
        for right, x in enumerate(nums):
            prod *= x
            while prod >= k:
                prod //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

var numSubarrayProductLessThanK = function(nums, k) {
  if (k <= 1) return 0;
  let left = 0, ans = 0, prod = 1;
  for (let right = 0; right < nums.length; right++) {
    prod *= nums[right];
    while (prod >= k) {
      prod /= nums[left++];
    }
    ans += right - left + 1;
  }
  return ans;
};