二ポインタ
2 ポインタ法は、整列済み配列から和が目標値になる二要素を探します。配列の両端に添字を置き、現在の和と目標を比較して、答えに使えない側を除外します。時間計算量は O(n)、追加領域は O(1) です。
整列済みなら、一回の比較で複数の組を除外できます。両端の和が大きすぎる場合、右端をほかの要素と組み合わせても大きすぎます。現在の左端が区間内の最小値だからです。和が小さすぎる場合は、左端をほかの要素と組み合わせても届きません。現在の右端が最大値だからです。
2 ポインタの仕組み
初期区間は [lo, hi]、添字は lo = 0、hi = n − 1 です。各反復で次を行います。
- 両端から
sum = nums[lo] + nums[hi]を計算します。 sumとtargetを比較します。- 一致すれば
[lo, hi]を返します。sum < targetならlo += 1、sum > targetならhi −= 1とします。
ループ条件は lo < hi です。二つの添字を別の位置に保ちます。一致しない反復では端点を一つ除外するため、移動は最大 n − 1 回です。ポインタが出会っても一致しなければ [-1, -1] を返します。
端点を除外できる理由
sum > target のとき、nums[hi] は nums[lo..hi] の最大値、nums[lo] は最小値です。右端を区間内の別の値と組み合わせると、和は現在以上になります。したがって、右端を含む候補を一回の移動ですべて除外できます。sum < target なら、同じ理由で nums[lo] を含む候補を除外できます。
n 要素から異なる二位置を選ぶ組は C(n, 2) 個です。総当たりは各組を調べます。2 ポインタは端点に対応する候補をまとめて除外し、最大 n − 1 回の移動で終了します。プレイヤーの候補数カウンターで、一回の移動が除外する組数を確認できます。
未整列の入力ではこの推論が成立しません。左端が最小、右端が最大とは限らず、除外した端点が区間内の要素と答えを作る可能性があります。
2 ポインタのステップ
初期入力は nums = [1, 4, 6, 8, 11, 15]、目標は target = 14 です。
lo = 0、hi = 5で、1 + 15 = 16です。16 > 14なので 15 を除外し、hi = 4にします。lo = 0、hi = 4で、1 + 11 = 12です。12 < 14なので 1 を除外し、lo = 1にします。lo = 1、hi = 4で、4 + 11 = 15です。和が大きすぎるのでhi = 3にします。lo = 1、hi = 3で、4 + 8 = 12です。和が小さすぎるのでlo = 2にします。lo = 2、hi = 3で、6 + 8 = 14です。一致したので添字[2, 3]を返します。
六要素には C(6, 2) = 15 個の候補がありますが、今回は五つの和を調べました。候補を端点ごとに除外するため、すべての組の和を求める必要はありません。
アニメーションでは両端を結ぶ括弧に現在の和が表示され、ポインタの接近に応じて縮みます。除外された端点は薄くなり、候補数カウンターが更新されます。一致した二要素は緑になります。
時間・空間計算量
| 場合 | 時間 |
|---|---|
| 最良：最初の両端で一致 | O(1) |
| 平均 | O(n) |
| 最悪：答えが中央付近、または存在しない | O(n) |
追加領域は O(1) で、添字を二つ保持します。未整列の入力を先に整列するなら、通常 O(n log n) の時間がかかります。和を満たす組を探すだけなら、平均 O(n) 時間、O(n) 領域のハッシュ法も選べます。2 ポインタ法は、整列済みデータや、別の目的でも整列が必要な場面に適しています。
境界条件
- 空配列・一要素：最初から
lo < hiが偽なので、[-1, -1]を返します。 - 両端が答え：
nums[0] + nums[n−1]が目標に一致すれば、一回の確認で終了し、移動はありません。 - 答えがない：ポインタが出会うまで進み、
[-1, -1]を返します。 - 重複値：同値同士も組にできますが、添字は異なる必要があります。
- 複数の答え：走査中に見つけた一組を返します。全列挙や一意性の保証はしません。
よくある間違い
- 未整列のまま使う：端点が極値とは限らず、答えを除外する場合があります。未整列のシナリオでは
1 + 8 = 9を見落とし、[-1, -1]を返します。先に整列するか、ハッシュ法を使います。 - ポインタの移動方向を逆にする：和が大きすぎる場合は
hiを左へ動かします。loを右へ動かしても和は小さくなりません。和が小さすぎる場合はloを右へ動かします。 lo <= hiにする：ポインタが出会うと同じ位置を二回使ってしまいます。厳密な<が異なる添字を保証します。- 整列の費用や元の添字を忘れる：存在確認だけなら、未整列データにハッシュ集合を使えます。整列後に位置を返す場合は、整列後の添字と元の添字を区別します。