Skip to content

不定长滑动窗口求短 Variable Sliding Window Subarrays Shorter

Table of Contents

713. Subarray Product Less Than K

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Sliding Window, Prefix Sum

from typing import List


# Sliding Window Variable Subarrays Shorter
def numSubarrayProductLessThanK(nums: List[int], k: int) -> int:
    if k <= 1:
        return 0

    left = 0
    prod = 1
    res = 0

    for right in range(len(nums)):
        prod *= nums[right]

        while prod >= k:
            prod //= nums[left]
            left += 1

        res += right - left + 1

    return res


if __name__ == "__main__":
    assert numSubarrayProductLessThanK([10, 5, 2, 6], 100) == 8
    assert numSubarrayProductLessThanK([1, 2, 3], 0) == 0
    assert numSubarrayProductLessThanK([1, 2, 3], 1) == 0
    assert numSubarrayProductLessThanK([1, 2, 3], 2) == 1
    assert numSubarrayProductLessThanK([1, 2, 3], 3) == 3

3258. Count Substrings That Satisfy K-Constraint I

2302. Count Subarrays With Score Less Than K

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Sliding Window, Prefix Sum

2762. Continuous Subarrays

  • LeetCode | 力扣

  • Tags: Array, Queue, Sliding Window, Heap Priority Queue, Ordered Set, Monotonic Queue

3134. Find the Median of the Uniqueness Array

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Binary Search, Sliding Window

3261. Count Substrings That Satisfy K-Constraint II

  • LeetCode | 力扣

  • Tags: Array, String, Binary Search, Sliding Window, Prefix Sum

2743. Count Substrings Without Repeating Character 👑