Minimum Size Subarray Sum
正の整数 target と、正の整数の配列 nums が与えられます。合計が target 以上となる最短の部分配列（隣り合う要素の連続した並び）を見つけ、その長さを返してください。どの部分配列の合計も target に達しない場合は、0 を返してください。
関数
- targetinteger
- 部分配列が達するか超える必要のある合計
- numsinteger-array
- 正の整数の配列
- 戻り値integer
- 合計が target 以上となる最短の部分配列の長さ。存在しない場合は 0。
制約
1 ≤ target ≤ 1091 ≤ nums.length ≤ 2 × 1041 ≤ nums[i] ≤ 104
例
- 入力
- target = 15nums = [4, 2, 9, 3, 7, 1, 5]
- 出力
- 3
- 説明
- 隣り合う2つの数では15に達しません。最も大きい組み合わせでも9 + 3 = 12です。3つなら達します。4 + 2 + 9 = 15、9 + 3 + 7 = 19なので、答えは3です。
- 入力
- target = 11nums = [1, 2, 3, 4]
- 出力
- 0
- 説明
- 配列全体の合計は10で、11未満なので、目標値に達する部分配列はなく、答えは0です。
- 入力
- target = 8nums = [3, 8, 2]
- 出力
- 1
- 説明
- 値 8 はそれ自体で目標値に達し、要素が 1 つより短い部分配列はありません。
提出時に隠しテスト+16件
発展問題
スライディングウィンドウが機能しなくなるような、nums にゼロや負の数も含まれる場合は、どのように解決しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての値は正です。部分配列の右端に要素を1つ追加すると和はどうなり、左端から要素を1つ削除するとどうなりますか？
ウィンドウ
nums[left..right]とその合計を保持します。合計がtargetに達するまで、右側に広げます。すると、そのウィンドウが候補となり、さらに短くできるか試せます。合計が
target以上である間、ウィンドウの長さを記録し、nums[left]を取り除きます。両端は右にしか動かないため、各要素はウィンドウに一度入って一度出ます。
解説
値はすべて正なので、部分配列を延長すると合計は必ず増え、切り詰めると必ず減ります。この事実ひとつが、どちらの高速な解法も成り立たせています。累積和は昇順のリストになるため、二分探索で合計が初めてtargetに達する位置を見つけられます。さらに、開始位置を右に動かしても最適な終点が左に戻ることはないので、右に広げて左を縮める単一のウィンドウを使えば、1回の走査で答えを見つけられます。
すべての開始位置から拡張する
正しいが、最大のテストでは終わらない
考え方
開始位置を固定し、右方向へ値を一つずつ加えていきます。累積和が初めて target に達したとき、その開始位置から始まる最短の部分配列が見つかります。それより短い部分配列はすべて、累積和がまだ小さいまま手前で終わっているからです。そこでその長さを記録し、延長をやめて次の開始位置に移ります。答えは、すべての開始位置における長さの最小値です。
target = 15、[4, 2, 9, 3, 7, 1, 5] の場合、開始位置 0 では和が 4、6、15 となり、長さ 3 で終了します。開始位置 1 では和が 2、11、14、21 となり、長さ 4 で終了します。開始位置 2 では和が 9、12、19 となり、再び長さ 3 です。どの開始位置でも 3 より短くなりません。
問題になるのは、目標値に到達するのが難しい場合です。どの部分配列も目標値に達しなければ、すべての開始位置で配列の末尾まで進むことになります。加算回数は n(n+1)/2 回で、n = 2 × 10^4 のとき 2 × 10^8 回です。また、各開始位置で、直前の開始位置ですでに計算した和を再計算してしまいます。
アルゴリズム
bestを 0 に設定します。まだ何も見つかっていないことを意味します。- 開始インデックスごとに、累積和を 0 に設定します。
- 終了インデックスを開始位置から右へ進めながら、
nums[end]を累積和に加えます。 - 累積和が
targetに達したら、end-start+1がbestを上回る場合はその値を保持し、この開始位置からの探索を終了します。 bestを返します。
def minSubArrayLen(target, nums):
n = len(nums)
best = 0 # 0 means no subarray found yet
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
if total >= target:
# The shortest subarray from this start ends here
if best == 0 or end - start + 1 < best:
best = end - start + 1
break
return best累積和と二分探索
考え方
prefix[k]を最初のk個の値の合計とし、prefix[0] = 0とします。このとき、nums[start..end-1]の合計はprefix[end] - prefix[start]です。開始位置を固定したとき、prefix[end] ≥ prefix[start] + targetを満たす最小のendを求めます。
すべての値が正なので、prefixは狭義単調増加します。したがって、ある値以上になる最初の位置は二分探索で求められます。[4, 2, 9, 3, 7, 1, 5]の場合、prefixは[0, 4, 6, 15, 18, 25, 26, 31]です。開始位置2からは6 + 15 = 21が必要です。21以上となる最初のprefixはインデックス5の25なので、区間はnums[2..4] = 9, 3, 7で、長さは3です。
prefix[n]でさえ、ある開始位置で必要な値に届かない場合、その開始位置では条件を満たす終了位置はありません。また、prefix[start]は増加するだけなので、それより後の開始位置でも条件を満たす終了位置はありません。そこで探索を終了します。二分探索をn回行うため、時間計算量はO(n log n)で、prefix配列にはさらにO(n)が必要です。比較される最大の値は2 × 10^8 + 10^9で、32ビット整数に収まります。
アルゴリズム
- 長さ
n+1のprefixを作成し、prefix[k+1] = prefix[k] + nums[k]とします。 - 各開始位置について、
need = prefix[start] + targetを計算します。 prefix[n] < needの場合、終了します。これより後の開始位置では条件を満たせません。start+1からnまでの位置を二分探索し、prefix[end] ≥ needとなる最初のendを見つけます。これまでで最短ならend-startを記録します。- 最短の長さを返し、条件を満たす開始位置がなければ0を返します。
from bisect import bisect_left
def minSubArrayLen(target, nums):
n = len(nums)
# prefix[k] is the sum of the first k values; it only grows
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 0
for start in range(n):
need = prefix[start] + target
if prefix[n] < need:
break # no window from here on can reach target
# The first end with prefix[end] >= need closes the shortest window
end = bisect_left(prefix, need, start + 1)
if best == 0 or end - start < best:
best = end - start
return bestスライディングウィンドウ
考え方
ウィンドウ nums[left..right] とその合計を保持します。right を一度に1つずつ進め、新しい値を加えます。合計が target 以上である間、そのウィンドウは候補です。長さを記録し、次に nums[left] を取り除いて left を進め、より短いウィンドウでも条件を満たすか確認します。
left を二度と戻さなくてよいのはなぜでしょうか？ウィンドウ nums[left..right] が初めて target に達したとき、より小さいウィンドウ nums[left..right-1] は達していません。達していたなら、前のステップでループがウィンドウを縮めていたはずだからです。つまり、この開始位置に対して right が最も早い終了位置であり、それ以降の終了位置では部分配列が長くなるだけです。この開始位置で得られる最善の答えはすでに見つかっています。この議論には正の値が必要です。負の数があると、より長いウィンドウの合計が後から大きくなる可能性があります。
target = 15、[4, 2, 9, 3, 7, 1, 5] の場合：合計は4、6、15と増えるため、長さ3を記録し、4を取り除きます（11）。3を加えると14、7を加えると21になります。長さ4を記録し、2を取り除くと（19）、長さ3を記録し、9を取り除きます（10）。1と5を加えると16になるため、長さ4を記録し、3を取り除きます（13）。答えは3です。
while ループは for ループの中にありますが、各インデックスはウィンドウに一度だけ入り、一度だけ取り除かれるため、全体の処理量は O(n) です。保存する数値は3つだけなので、空間計算量は O(1) です。
アルゴリズム
left = 0、total = 0、best = 0を設定します。- 各
rightについて、nums[right]をtotalに加えます。 total ≥ targetである間、right-left+1がbestを上回る場合はbestを更新し、nums[left]を引いてleftを右に1つ進めます。bestを返します。合計がtargetに達しなかった場合、値は0のままです。
def minSubArrayLen(target, nums):
best = 0 # 0 means no window found yet
total = 0 # sum of nums[left .. right]
left = 0
for right in range(len(nums)):
total += nums[right]
# Shrink while the window still reaches target
while total >= target:
if best == 0 or right - left + 1 < best:
best = right - left + 1
total -= nums[left]
left += 1
return best
落とし穴と境界ケース
バグの大半は、ウィンドウを縮める手順と、targetに達するものがない場合に返す値にあります。
whileではなくifでウィンドウを縮めている。target = 12で[1, 1, 2, 3, 12]の場合、12を加えると合計は19になります。ifでは長さ5を記録し、値を1つ削除して次に進むため、長さ1のウィンドウ[12]は一度も測定されません。合計がまだ十分な間は削除し続けるループを使いましょう。nums[left]を削除した後に長さを記録している。測定するウィンドウは、合計がtargetに達したときのものでなければなりません。≥ではなく>で比較している。合計がtargetと等しい部分配列も数えます。target = 9での[3, 3, 3]の答えは0ではなく3です。- 番兵値をそのまま返している。
bestをn+1または無限大で初期化した場合、targetに達するものがなければ0に変換してください。 - 0や負の数を含む配列で、同じウィンドウ処理を使っている。この方法はすべての値が正であることを前提としており、この問題では保証されていますが、派生問題では保証されません。
よくある質問4
Minimum Size Subarray Sum の時間計算量は何ですか？
スライディングウィンドウ解法は、時間計算量がO(n)、空間計算量がO(1)です。内側のループによって計算量が二次になりそうに見えますが、leftは前に進むだけなので、全体を通して進む回数は最大でもn回です。累積和を使う方法はO(n log n)で、すべての開始位置を調べる方法はO(n²)です。
なぜスライディングウィンドウには正の数が必要なのですか？
ウィンドウを縮小すると合計が小さくなり、拡大すると大きくならなければなりません。そうでないと、左端の要素を取り除いたときに答えの先頭部分まで捨ててしまう可能性があります。負の数があると、この順序関係は成り立ちません。一般的な解決策は、候補となる開始位置を単調デックで管理しながら累積和を使う方法で、これでも O(n) で実行できます。
O(n)の解法があるのに、なぜO(n log n)の累積和による解法を学ぶのでしょうか？
面接官は、O(n)の解答の後によくこれを尋ねます。これは、正の値の別の使い方を示しています。累積和はソートされているため、二分探索で累積値がしきい値を初めて超える位置を見つけられます。この手法は、重みに比例した確率でランダムにインデックスを選ぶなど、ほかの問題でも再び登場します。
部分配列の合計は、目標値と正確に一致する必要がありますか？
いいえ。target以上の合計であれば、どれでも該当します。target = 15の場合、9、3、7のウィンドウの合計は19で、長さは3のままです。合計がちょうど一致する必要がある場合でも、正の値ならこのウィンドウは機能します。合計が目標値を上回っている間はウィンドウを縮小し、合計が一致したときにだけ長さを記録します。
Python
def minSubArrayLen(target, nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
期待値
3