デュエットのパートナーをどう選ぶ？
歌の練習アプリ「ハーモニー」では、メンバーごとに音程スコアがあります。2人で歌うとき、2つのスコアの和が目標ハーモニー値Tに近いほど、デュエットがよく合います。
ところが、和がちょうどTになる2人がいないこともあります。だから目標は「和がTになるペア」ではなく、「和がTに最も近いペア」を見つけることです。
例: スコアが
[12, 18, 25, 33, 41, 50]、目標が60なら？ 答えは59 (18 + 41)。 差がわずか1で最も近いです。
最も単純な方法とその限界
まず思いつくのは、すべての2人の組み合わせを試すことです。和を求めて |和 - T| が最小のペアを覚えればよい。
問題は、メンバーがN人なら組み合わせが約N²/2個あること。Nが10万なら50億回 — 時間内に終わりません。O(n²)は遅すぎます。
核心アイデア: ソートを武器に（両端の二点探索）
ここに重要な前提があります。スコアが昇順にソート済みであることです。これを利用すれば、すべてのペアを見なくても答えが見つかります。
ポインタ2つを両端に置いて始めます。
- •
leftは最小値（左端）、rightは最大値（右端）を指す - •2つの値の和を目標Tと比較します:
- 和 < T → 小さすぎる → より大きな値が必要 → left を右へ1つ
- 和 > T → 大きすぎる → より小さな値が必要 → right を左へ1つ
- 和 == T → 差0、これ以上近づけないので即答え
- •ペアごとに |和 - T| をこれまでの最良と比べ、より近ければbestを更新します。
これを left と right が出会うまで繰り返せば終わりです。
「なぜ片方だけ動かして安全なのか？」
最初は「片方のポインタだけ動かすと見逃すペアが出ないか？」と心配になります。でもソート済みだから安全です。
和がTより小さい場合を考えてみましょう。いま right は右端なので、可能な限り大きな値と組んでいます。それでも和が小さいなら、right を減らして作るペアは和がさらに小さくなるだけ — Tに近づくことは決してありません。だからそれらのペアは捨てて安全で、和を大きくする唯一の手段である left++ だけすればよいのです。
和がTより大きい場合も対称に同じ理屈が成り立ちます。だから各ポインタは一方向にだけ動き、全体がO(n)で終わります。
ひと目でわかる計算量
| 方法 | 時間計算量 | 備考 |
|---|---|---|
| 全ペア比較 | O(n²) | 単純だがNが大きいと不可 |
| 両端の二点探索 | O(n) | ソート前提、各ポインタ一方向移動 |
| (未ソートなら) | O(n log n) | 先にソートしてから二点探索 |
よくあるミス
- •bestの初期化漏れ: 最初のペアをbestに入れておかないと比較の基準がありません。
- •差を絶対値で比較しない: 必ず |和 - T| で比較し、上下どちらも公平に扱います。
- •ソート確認漏れ: 入力がソート済みと保証されないなら、先にソートします。
- •終了条件の誤り:
left < rightの間だけ繰り返し、同じ人を2回選ばないようにします。
AlgoNoteで直接確認しましょう
2つのポインタが両端からどう絞り込むのか、そしてbestが更新される瞬間は、目で見てこそ確実に理解できます。和が目標より大きいとき・小さいときにポインタがどう反応するか、1ステップずつ追ってみてください。