尺取り法、累積和、二分探索で209. Minimum Size Subarray Sum

総和がtarget以上になるような最小の部分列の長さを求める問題。

Just a moment...

公式の最適解は2 pointersで、O(N)で解ける。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = float('inf')
        l = 0
        val = 0
        for i in range(n):
            val += nums[i]
            while val >= target:
                ans = min(ans, i - l + 1)
                val -= nums[l]
                l += 1

        if ans == float('inf'):
            ans = 0

        return ans

別解がいくつかあるので、考えてみる。

尺取り法

forループを使わない2 pointersに近い。

全ての要素を1度見れば済むので、時間計算量はO(N)。

ポインタと答えを保存する変数しか使わないので、空間計算量はO(1)。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if sum(nums) < target:
            return 0

        n = len(nums)
        l = -1
        r = -1
        curr = 0
        ans = float('inf')
        while r < n:
            if l > r:
                r = l
                curr = 0
                continue

            if curr < target:
                r += 1
                if r >= n:
                    break
                curr += nums[r]
            else:
                l += 1
                curr -= nums[l]
                ans = min(ans, r - l + 1)

        if ans == float('inf'):
            ans = 0

        return ans

部分和がtargetより小さければrightを進め、大きければleftを進める。

left が right を追い越したらリセット。

            if l > r:
                r = l
                curr = 0
                continue

ポインタの初期値を-1にすることで、「今いる場所までの和」の計算が楽になる。

0スタートにすると、足し引きしてからポインタを進める→長さの計算という流れになり、r-l+1ではなくなって直感に反する。

            if curr < target:
                r += 1
                if r >= n:
                    break
                curr += nums[r]
            else:
                l += 1
                curr -= nums[l]
                ans = min(ans, r - l + 1)

累積和

部分和の問題は累積和を取ることで計算量を落とせることが多い。

今回の問題も累積和をあらかじめ計算してから全探索することで計算量をO(n^3)からO(N^2)に落とすことが出来る。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)

        cumsum = [0] * (n + 1)
        for i in range(1, n + 1):
            cumsum[i] = cumsum[i - 1] + nums[i - 1]

        ans = float('inf')
        for i in range(n + 1):
            for j in range(i, n + 1):
                val = cumsum[j] - cumsum[i]
                if val >= target:
                    ans = min(ans, j - i)

        if ans == float('inf'):
            ans = 0

        return ans

二分探索

制約条件から与えられる配列は正の値のみからなるので、累積和は単調増加となる。

累積和をソート済みの配列だと考えると、二分探索を使うことができそう。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)

        cumsum = [0] * (n + 1)
        for i in range(1, n + 1):
            cumsum[i] = cumsum[i - 1] + nums[i - 1]

        ans = float('inf')
        for i in range(n, -1, -1):
            if cumsum[i] < target:
                break

            l = -1
            r = i + 1
            while r - l > 1:
                mid = (l + r) // 2
                if cumsum[i] - cumsum[mid] >= target:
                    l = mid
                else:
                    r = mid

            ans = min(ans, i - l)

        if ans == float('inf'):
            ans = 0

        return ans

累積和がtarget以下の場合、部分和もtarget以下になる。

途中で処理を打ち切ると定数倍高速化できるので、forループは逆順で回す。

        for i in range(n, -1, -1):
            if cumsum[i] < target:
                break

めぐる式二分探索を行う。

求める答えは最小の長さなので、部分和がtarget以上になるような最大のleftを探せば良い。

累積和と使った部分和の長さはr-l+1ではなくr-lなのに注意。

            l = -1
            r = i + 1
            while r - l > 1:
                mid = (l + r) // 2
                if cumsum[i] - cumsum[mid] >= target:
                    l = mid
                else:
                    r = mid

            ans = min(ans, i - l)

前処理の累積和の計算がO(N)、メインの二分探索+ループがO(N logN)となり、遅い方のO(N logN)が時間計算量。

空間計算量は累積和の配列を用意するためO(N)。

最適解ではないが、累積和をソート済み配列だと考えるのが面白かった。

コメント

タイトルとURLをコピーしました