Longest Subarray with Sum K
整数numsと目標値kが与えられたとき、要素の合計がちょうどkになる最長の部分配列の長さを返してください。部分配列とは、連続する要素を少なくとも1つ含む範囲です。値には0以下のものが含まれる場合があります。合計がkになる部分配列がない場合は、0を返してください。
関数
- numsinteger-array
- 検索する整数（負の数とゼロを含む）
- kinteger
- 部分配列が持つべき正確な合計値
- 戻り値integer
- 合計がkになる最長の部分配列の長さ。該当するものがない場合は0
制約
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104-109 ≤ k ≤ 109- すべての累積和は
-2 × 108から2 × 108の範囲内に収まるため、32ビット整数で十分です。 - 合計が
kになる部分配列がない場合は0を返します。
例
- 入力
- nums = [2, -1, 3, 1, -4, 2, 3]k = 5
- 出力
- 5
- 説明
- 3つの連続区間の合計はいずれも5です。末尾の
[2, 3]、先頭の[2, -1, 3, 1]、そしてインデックス2から6までの[3, 1, -4, 2, 3]です。最後のものが最も長く、要素数は5です。
- 入力
- nums = [4, 1, 1, 2, -1, 1]k = 3
- 出力
- 4
- 説明
- インデックス1〜4の
[1, 1, 2, -1]とインデックス2〜5の[1, 2, -1, 1]は、どちらも4個の要素で合計が3になります。返すのは長さなので、同点でも問題ありません。
- 入力
- nums = [-3, 6, -3]k = 1
- 出力
- 0
- 説明
- 6つの部分配列の合計は、-3、6、-3、3、3、0です。そのうち1であるものはないため、答えは0です。
発展問題
負の値も引き続き許容される場合、合計が最大でもkとなる最長の部分配列をどのように見つけますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数値が20,000個あると、総当たりでは開始位置と終了位置の組み合わせが約2 × 10^8個になります。負の値がある場合も、スライディングウィンドウは使えません。合計が
kを超えた区間でも、後から再びk以下になることがあるためです。1回の引き算で任意の部分配列の合計を求められるようにするには、どの累積合計を使えばよいでしょうか？累積和を計算しておくと、位置
iの次から位置jまでの要素の合計はprefix[j] - prefix[i]になります。jで終わる部分配列の合計がkになるのは、それより前の累積和がprefix[j] - kと等しいときです。条件に合うそれより前の累積和が複数ある場合、どれを選べば部分配列が最も長くなりますか？各累積合計について、最初に現れたインデックスを記録します。合計 0 はインデックス -1 から始まります。各インデックスで、
prefix - kを検索し、その距離をこれまでの最長の長さと比較します。現在の累積合計がまだマップにない場合にのみ、マップに追加します。
解説
累積和を使うと、任意の部分配列の合計を1回の引き算で求められます。インデックス s の次からインデックス i までの要素の合計は prefix[i] - prefix[s] です。それぞれの合計が最初に現れたインデックスを記録しておけば、1回の走査で各位置で終わる最長の一致を見つけられます。
各開始位置からすべての部分配列を伸ばす
正しいが、最大のテストでは終わらない
考え方
各開始位置から右方向に延長し、要素を累計に加えていきます。累計が k と等しくなったら、長さを記録します。すべての部分配列は開始位置と終了位置の1組で表されるため、見落としはありません。累計が k を超えても延長を続けます。最初の例のインデックス2からは累計が3、4、0、2、5となり、最後に5に達するのは-4があるためです。
組み合わせは約 n²/2 個あります。n = 2 × 10^4 の場合、加算は 2 × 10^8 回です。
アルゴリズム
bestを0に設定します。- 各
startについて、totalを0に設定します。 endをstartから最後のインデックスまで移動させ、nums[end]をtotalに加算します。totalがkと等しいとき、bestとend - start + 1の大きい方をbestに設定します。bestを返します。
def longestSubarrayWithSumK(nums, k):
n = len(nums)
best = 0
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
# A match may come after the total has passed k, so never stop early
if total == k and end - start + 1 > best:
best = end - start + 1
return best各累積和の最初のインデックスを使った累積和
考え方
インデックス i で終わる連続区間の合計が k になるのは、それより前の累積合計の中に prefix - k がある場合です。条件を満たす累積合計が複数ある場合、最初に現れたものが最も長い連続区間の開始位置になるため、マップには各累積合計を最初に出現したときだけ格納します。後から現れた同じ値を使っても、より短い連続区間しか開始できません。インデックス -1 の累積合計を 0 としてマップに登録しておくと、インデックス 0 から始まる一致の長さが i + 1 になります。
最初の例では、累積合計は 2, 1, 4, 5, 1, 3, 6 です。インデックス 6 では、6 - 5 = 1 が最初にインデックス 1 で現れているため、長さは 5 になります。累積合計 1 はインデックス 4 で再び現れますが、インデックス 1 を保持しておくことで、その連続区間を見つけられます。
要素ごとの検索は 1 回なので、時間計算量は O(n) であり、マップには最大 n + 1 個の累積合計が格納されます。
アルゴリズム
- 合計 0 をインデックス -1 で保持するマップ
firstを作成し、prefixとbestを 0 に設定します。 - 各インデックス
iについて、nums[i]をprefixに加えます。 prefix - kがマップ内のインデックスstartにある場合、bestをbestとi - startの大きい方に設定します。prefixがまだマップにない場合は、インデックスiとともに保存します。bestを返します。
def longestSubarrayWithSumK(nums, k):
# first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
first = {0: -1}
prefix = 0
best = 0
for i, num in enumerate(nums):
prefix += num
# The earliest prefix equal to prefix - k starts the longest match that ends at i
start = first.get(prefix - k)
if start is not None and i - start > best:
best = i - start
# Keep the first index only: a later one could only start a shorter subarray
if prefix not in first:
first[prefix] = i
return best
落とし穴と境界ケース
- 合計値が繰り返されるたびに保存済みのインデックスを上書きすると、最新の開始位置が保持され、より短い一致が見つかります。最初の例では、合計値 1 がインデックス 1 からインデックス 4 に移動するため、5 ではなく 4 が返されます。
- 合計値が
kを上回っている間にウィンドウを縮小する場合も、最初の例では 4 が返されます。合計値が 4 の[-1, 3, 1, -4, 2, 3]を保持した状態で終了し、-1 は取り除かれません。 - インデックス -1 における合計値 0 を省くと、インデックス 0 から始まるすべての一致を見逃します。
[5, 0, 0, 0]でk = 5の場合、4 ではなく 0 が返されます。 - 保存されたインデックスは部分配列の直前の位置なので、長さは
i - startです。1 を足すと、要素を1つ多く数えてしまいます。
よくある質問3
和がKである最長部分配列の時間計算量は何ですか？
累積合計と最初のインデックスのマップを使うと、時間計算量は O(n)、追加の空間計算量は O(n) です。各要素につき、検索は1回、挿入は最大1回です。各開始位置からすべての部分配列を伸ばしていくと、時間計算量は O(n²)、空間計算量は O(1) です。
配列に負の数が含まれていると、スライディングウィンドウがうまく機能しないのはなぜですか？
スライディングウィンドウでは、要素を追加すると合計が増え、要素を削除すると合計が減ると仮定します。負の値がある場合、合計が大きすぎるウィンドウでも、負の要素が加わるとkに到達することがあり、合計が小さすぎるウィンドウでは、左端の負の要素を削除する必要があるかもしれません。ウィンドウだけでは、どちらの操作が適切か判断できません。
合計が K となる最長の部分配列は、追加の O(1) 空間で解けますか？
値がすべて非負の場合に限ります。その場合、ウィンドウが広がっても合計は減少せず、2つのポインターを使って、合計が k となる最長のウィンドウを O(n) 時間、O(1) 空間で見つけられます。負の値がある場合は、合計値のマップを使うか、O(n²) で走査する必要があります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestSubarrayWithSumK(nums, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, -1, 3, 1, -4, 2, 3] k = 5
期待される出力
5