3Sum（3つの数の和）
3Sum（3つの数の和）とは
整数配列から、合計が0になる重複しない三つ組をすべて見つける課題です。
ソート後の順序を利用して、探索範囲を動かす考え方を学べます。
判断するときに確認すること
- 同じ三つ組を重複して返していないか
- ポインターを動かす条件が正しいか
- ソートの計算量を含めているか
具体例で整理する
避けたい判断
三重ループで全組合せを調べ、重複を後から複雑に除去する。
条件が分かる判断
固定値と左右の合計が小さければ左、大きければ右を動かす。
設計とレビューで使う
このページの推奨は次のとおりです。
配列をソートし、一つを固定して残りを左右のポインターで探索する。