アルゴリズム・データ構造図鑑 · 基礎から応用へ

二つの端から、和になる組を探す

整列順を使って候補をまとめて捨てる理由を追い、重複・元の添字・一要素だけの入力を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 二つの端から、残す候補を狭める
  2. 和が小さいときに左を捨てられる理由
  3. 一組を返す実装を読む
  4. 重複があるとき、何を数えるかを決める
  5. 未整列の反例を一つ作る
  6. 計算量は端の移動回数から数える
  7. 三つの値へ広げるときの費用
  8. 端の移動を説明する課題
  9. この記事をロゲイアに質問する理解を確かめる

二つの端から、残す候補を狭める

整列した配列から、和が目標値になる二要素を探します。配列は−2、0、1、3、5、目標は4としましょう。左端の−2と右端の5の和は3です。小さすぎるので左を進めると、0と5で5になります。今度は右を戻し、0と3で3、1と3で4へ到達します。同じ添字を二度使うことは認めません。値が同じでも、別の位置にある二要素なら組にできます。

この方法の中心は、二本の変数を置くことではありません。捨てる行や列に答えが残らない理由を、整列順から説明することです。初めに全組を表へ並べ、調べる範囲の左下と右上を動かすつもりで追ってください。配列を一度整列する費用を含めるか、すでに整列した入力を受け取るかで、処理全体の計算量は変わります。

和が小さいときに左を捨てられる理由

現在の左右をL、Rとし、a[L]+a[R]が目標より小さいとします。Rはまだ残っている最大の値です。したがって、a[L]へLより右でR以下のどの値を足しても、目標に届きません。Lを使う組を全て捨ててよく、Lを一つ進められます。Lを残したまま右を戻しても、和は増えません。端を動かす判断は、目標との差の大きさではなく、この単調な順序に基づきます。

和が大きい場合は逆です。Lは残る最小値なので、Rへそれ以上のどの値を足しても大きすぎます。Rを使う組を捨て、右を一つ戻します。負数が含まれても、値の整列順は変わらないため、この証明は成立します。負数があると使えなくなる区間和の窓とは、必要な条件が異なります。二つの技法の見た目だけで適用条件を共有しないようにします。

現在の和除ける候補次の操作
目標より小さい現在の左端を使う組leftを増やす
目標より大きい現在の右端を使う組rightを減らす
目標と等しい有効な異なる二位置を発見その組を返す

一組を返す実装を読む

実装は整列済みの入力を受け、見つけた添字の組かNoneを返します。left<rightの間だけ調べるので、一要素だけの配列で自分自身を相手にしません。空配列でもループへ入りません。Pythonの整数を使うため加算の固定幅オーバーフローはありませんが、別の言語へ移すときは比較の前に加算が範囲を越えないかを確認してください。入力の整列を実装が検査していないことも、呼出し側との契約です。

付属の検査では、−2から2の整列された多重集合を長さ0〜6で作り、全ての添字組を調べる参照解と比較します。返った組があるかだけでなく、添字が異なり和が一致することもassertします。参照解は遅くても小入力では読みやすく、速い実装と同じ端の動かし方を繰り返さないため、別の誤りを見つける助けになります。

python
from itertools import combinations_with_replacement
def pair(a,target):
    left=0;right=len(a)-1
    while left<right:
        total=a[left]+a[right]
        if total==target:return (left,right)
        if total<target:left+=1
        else:right-=1
    return None
for n in range(7):
    for a in combinations_with_replacement(range(-2,3),n):
        for target in range(-5,6):
            result=pair(a,target)
            exists=any(a[i]+a[j]==target for i in range(n) for j in range(i+1,n))
            assert (result is not None)==exists
            if result:assert result[0]<result[1] and a[result[0]]+a[result[1]]==target
assert pair([3],6) is None and pair([3,3],6)==(0,1)
print('sorted multisets lengths0..6 matched brute force')

重複があるとき、何を数えるかを決める

3、3という二要素と目標6なら、添字0と1が答えです。一方、3が一つだけなら答えはありません。「値の組を一種類返す」「添字の組を全て返す」「組の数だけ返す」は別の問題です。3が四つある場合、値の組は一種類でも添字の組は六通りあります。一組を見つけたら終わる今回のコードを、そのまま組の数を数える実装として使うことはできません。

全組を列挙する場合は、同じ値が左右に何個あるかを数え、同値の扱いを決めます。出力する組が二次の個数になる入力では、列挙そのものにも時間がかかります。走査の端が各n回しか動かないことと、出力全体を線形時間で書けることは異なります。求める出力の定義を先に固定すれば、重複の除外や乗算で数える工夫が正しいか判断しやすくなります。

未整列の反例を一つ作る

配列1、4、2と目標5を、そのまま入力した場合を考えます。端の1と2は小さいので左を進め、4と2は大きいので右を戻すと、二つの端が重なって終了します。しかし添字0と1の1+4は答えです。最大値が右端にあるという証明の前提が失われたため、捨てた左端に答えが残っていました。反例では、単に失敗したと言うだけでなく、どの捨て方が根拠を失ったかを説明します。

整列し直すなら、元の添字を返す要件も考えます。値と元位置の組を整列すれば位置を保存できますが、追加領域や安定した出力の約束が必要になります。別の候補としてハッシュ表で相方を探す方法もあります。平均的な費用、メモリ量、入力を変更してよいか、必要な添字の順序を並べて、今回の前提へ合う方法を選びます。

計算量は端の移動回数から数える

各反復では左が一つ進むか、右が一つ戻ります。どちらも後戻りしないため、反復回数は高々n−1回で、整列済み入力に対する走査はO(n)です。使う追加の状態は左右の添字と現在の和だけなので、固定幅の値と添字を仮定すれば追加領域はO(1)です。Pythonの大きな整数を任意の桁数で扱う場合、加算や比較の費用まで常に定数とは言えません。ここでは通常の語長に収まる値を費用の基準とします。

整列が必要なら、通常はそのO(n log n)も処理全体へ含めます。同じ配列へ多数の目標を問い合わせる場合は、整列の一回分と各走査を分けて見積もれます。単純な二重ループとの比較では、入力生成や整列を計測区間へ含めたかを揃えます。測定の都合で整列済みの片方だけを有利にしないことが、アルゴリズムの選択を説明するうえで大切です。

三つの値へ広げるときの費用

三つの異なる添字の和を探す場合、一つの位置を固定し、その右側だけで二つの端を動かす構成を考えられます。固定した位置を相方へ使い直さないことが必要です。整列済み配列なら、固定位置をn通り試し、残る部分へ線形の走査を行うため、通常の基本形はO(n²)になります。端が一方向へ動く内側だけを見て、問題全体がO(n)のままだと説明しないでください。

重複する三つ組を一種類だけ返したい場合は、固定する値と両端の値の重複をどう飛ばすかも追加します。添字の三つ組を全て出す課題とは結果の数が異なります。二要素の正しさを再利用できる部分と、新しい出力契約や外側の反復で増えた費用を分けると、既知の技法を組み合わせる際の検証範囲が明確になります。

端の移動を説明する課題

課題は−3、−1、2、4、6、目標5の配列で、最初の三回の和と端の動きを記すことです。解答は−3+6=3で左を進め、−1+6=5で発見するため、三回目はありません。決めた反復回数を埋めるために、答えを見つけた後も架空の移動を続けないでください。発見時の添字は1と4です。左を捨てた根拠は、−3へ残るどの相手を足しても5へ届かないことです。

追加課題では目標を12へ変えます。6が一つだけなので6+6は許されません。解答は該当なしです。最後の一要素まで来てもleft<rightが偽なら終了します。値だけを見た答えと、異なる位置を必要とする仕様の答えが違うことを確認します。条件を変えるたびに、入出力契約、不変条件、停止条件の三つへ戻ると、似た問題へ正しく応用できます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ