49. Minimum Size Subarray Sum

読了目安約1分

Sliding Window / LeetCode 209 (Medium) — 和が target 以上になる最短の連続部分配列を尺取り法で求める。

この章の目次

問題

LeetCode 209. Minimum Size Subarray Sum（Medium / カテゴリ: Sliding Window）

正の整数の配列 nums と整数 target が与えられます。和が target 以上になる連続部分配列のうち、最短のものの長さを返します。そのような部分配列がなければ 0 を返します。

考え方

ヒント 1

要素がすべて正なので、区間を右に広げると和は必ず増え、左を縮めると必ず減ります。この単調性が、スライディングウィンドウ（尺取り法）を使える条件です。

ヒント 2

right を進めて和に足し、和が target 以上である間は「答えを更新してから left を縮める」を繰り返します。 left と right はそれぞれ最大 n 回しか進まないので、二重ループに見えても O(n) です。

Swift 実装のポイント

縮める処理は while sum >= target で書きます。if にすると縮め残しが出ます。
答えの更新は縮める前に行います。best = min(best, right - left + 1) をしてから sum -= nums[left] します。
最短長の初期値は Int.max にして、最後まで更新されなければ 0 を返します。

模範解答

Swift
class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var left = 0
        var sum = 0
        var best = Int.max
        for right in 0..<nums.count {
            sum += nums[right]
            while sum >= target {
                best = min(best, right - left + 1)
                sum -= nums[left]
                left += 1
            }
        }
        return best == Int.max ? 0 : best
    }
}

計算量: O(n)。