アルゴリズムは毎日1題を練習します:積はKのサブ配列より小さいです

713.積がKより小さいサブ配列
正の整数配列numsが与えられます.
この配列内の積がkより小さい連続するサブ配列の個数を探し出す.

例1:

入力:nums=[10,5,2,6],k=100出力:8解釈:8個の積が100未満のサブ配列はそれぞれ:[10],[5],[2],[6],[10,5],[5,2],[2,6],[5,26],[5,26]である.[10,5,2]は、積が100未満のサブ配列ではないことに注意されたい.
説明:

0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6

リンク:https://leetcode-cn.com/problems/subarray-product-less-than-k
問題解分析

題の要求出力は、サブ配列の個数であり、サブ配列の要素は連続的であり、積はk

以下であり、k に等しくない.

単一要素の配列も許容されるが、その値はk

未満である.

は、まず調整を満たすサブ配列を見つけてから、数を統計する.サブ配列list

を維持する必要はありません

要点はすべてのサブ配列を見つけることです.

は順次遍歴し、いずれかのiの値がkより小さい場合count+=1

連続性判定は、j=i,jを右に移動する

#        

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if not nums:
            return None
        count = 0 
        length = len(nums)
        for i in range(0,length):
            if nums[i] < k:
                count += 1
            j = i + 1
            mult = nums[i]
            while j < length:
                mult *= nums[j]
                if mult < k:
                    count += 1
                    j += 1
                else:
                    break
        return count

方法2:ダブルポインタ

分析

二分ルックアップを用いてこの問題を解決することができ,すなわち,固定iに対して,二分ルックアップはnums[i]からnums[j]までの最大jの積がk未満であることを見出した.しかし、積が非常に大きい(最悪の場合1000^50000に達すると数値オーバーフローを招く可能性があるため、nums配列に対して対数を取り、乗算を加算、すなわちlog⁡(∏inums[i])=Σilog⁡nums[i]に変換する必要があり、数値オーバーフローの問題は発生しない.

アルゴリズム

numsの各数に対して対数を取った後,その接頭辞とprefix,すなわちprefix[i+1]=Σnums[x]を格納し,二分ルックアップ時にiとjに対してprefix[j+1]−prefix[i]でnums[i]からnums[j]の積の対数を得ることができる.固定iの場合、最大の条件を満たすjが見つかった後、j−i+1個の積がk未満の連続サブ配列を含む.

#         
class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
            if k <= 1: return 0
            mult = 1
            count = left = 0
            for right, val in enumerate(nums):
                mult *= val
                while mult >= k:
                    mult /= nums[left]
                    left += 1
                count += right - left + 1
            return count