3Sum（LeetCode #15）

3Sum は和が零になる、値として重複しない三つ組をすべて返します。ソートし、一つを基準値に固定して後方を二ポインターで走査します。総当たり O(n³) から O(n²) へ減らし、隣接する同値を飛ばすので別の重複集合は不要です。

O(n log n) のソートは二つの条件を作ります。左が最小、右が最大となって候補の除外ができ、同値が並ぶため基準値と両ポインターで隣との比較を使えます。

3Sum の仕組み

三つ組の最小位置 nums[i] を基準にすると、残る二値の目標は need = -nums[i]。ソート済みの後続部分で二ポインター検索を実行します。lo は基準の直後、hi は末尾です。

和が need 未満なら、左値は最大の相手でも足りず lo を進めます。大きければ右値は最小の相手でも過大なので hi を戻します。一致なら [nums[i], nums[lo], nums[hi]] を記録します。

三つの詳細はすべて整列に依存します。

• 同じ基準値を飛ばす：i > 0 で nums[i] == nums[i - 1] なら、前回が同じ目標でより広い後方を調べ済みです。
• 一致後は両端を動かし、同値を飛ばす：一端を固定して片方だけ変えても、再一致は同値による重複です。両端の移動後、今使った値の連続コピーをそれぞれ飛ばします。
• 正の基準値で全体終了：nums[i] > 0 なら残りはそれ以上で、和はすべて正。break で基準ループを終えます。

解法をステップで追う

既定は nums = [-1, 0, 1, 2, -1, -4]。

1. ソート：[-4, -1, -1, 0, 1, 2]。二つの -1 が隣接する。
2. 添字 0、基準 -4、need = 4：-1 + 2 = 1、-1 + 2 = 1、0 + 2 = 2、1 + 2 = 3。すべて不足し、lo が hi に会って結果なし。
3. 添字 1、基準 -1、need = 1：-1 + 2 = 1 で [-1, -1, 2] を記録。両端を 0 と 1 へ動かし、重複はない。
4. 同じ基準を継続：0 + 1 = 1 で [-1, 0, 1]。動いたポインターが交差する。一基準から複数解を得られる。
5. 添字 2 の -1：左隣と等しいのでスキップ。候補は前回の部分集合。
6. 添字 3、基準 0、need = 0：唯一の 1 + 2 = 3 > 0 で hi を戻し、交わる。基準は n - 3 までで、それ以降は三位置を確保できない。
7. 完了：[[-1, -1, 2], [-1, 0, 1]]。各組は一回だけ。

紫の基準セル、ヘッダーの need、括弧と二ポインターで、一基準ごとの Two Sum を示します。除外したセルは薄く、基準より前は処理済みとして残します。ペアの検査ごとに tests が一つ増え、最大 n 基準 × O(n) の走査が O(n²) になります。

既定例は一致後の左右スキップを示しません。次の値がたまたま重複しないためです。設定の Duplicates everywhere で両端が同値列を飛ばす場面を見てください。この二ループがないと同じ三つ組を再記録します。

時間・空間計算量

ソートの O(n log n) は全走査 O(n²) に含まれます。定数空間は二ポインターの層だけで、出力とソートの作業領域を含みません。Python Timsort は最悪 O(n) の補助空間を使えます。入力上限八個、−20 から 20 は表示のためです。

目標は零以外でもよく、need = target - nums[i] に変えられます。早期終了も 3 * nums[i] > target に変えます。基準は三値の最小なので、和は 3 * nums[i] 以上です。nums[i] > 0 のままだと、[1, 2, 3]・target 6 は最初の基準で止まり、答えを逃します。k-sum も基準を固定して再帰し、最後の整列済み 2Sum を線形走査で解きます。値の重複を除き、ソート可能な時に使います。nums.sort() は入力順を変えるので、必要ならコピーを渡してください。

境界ケース

• 三値だけ：候補の三つ組は一つ。一ペア検査だが、先頭が正なら検査前に break する。
• 全正数：最初の基準で break、空リスト。
• 全負数：同じ空結果でも正の break は使わず、各走査が不足のまま尽きる。
• 全零：[0, 0, 0, 0, 0] は添字の組が十通りでも、値の組 [0, 0, 0] は一つ。
• 解なし：空リストを返す通常の結果。
• 一致の両側に重複：[-2, 0, 0, 1, 2, 2] は両スキップを使い、[-2, 0, 2] の重複を防ぐ。

よくある間違い

• 同じ基準を再実行する。 既定の二つ目の -1 が [-1, 0, 1] を再発見します。
• 一致後に片側だけ動かす。 同値でしか再成功しない候補を調べます。両端を動かして重複を飛ばします。
• ソート後も追加集合に頼る。 正しくても O(k) の記憶とハッシュが増えます。隣接規則で正規化された一意の結果が得られます。
• 入力の並べ替えを忘れる。 元の順序が必要ならコピーをソートします。
• 正の基準で continue。 正しいものの、無解と証明済みの後続も調べます。break で終了できます。
• 二値の和を 0 と比較する。 二値なら need、0 と比べるなら基準も加えます。二つの式を混ぜないでください。