2つのポインターのパターンは2つの位置を保ち、ルールに従ってそれらを動かすので、各項目は一度だけ訪れられます:入れ子の2重ループならO(n²)のところがO(n)です。
- 両端から:1つのポインターを先頭に、もう1つを末尾に置き、互いに近づけます。これで回文を確かめ、並べ替えたデータで与えられた合計になる組を見つけます:合計が小さすぎれば左のポインターを右へ、大きすぎれば右のポインターを左へ動かします。
- 並べて:リストごとに1つのポインターを置き、常に小さいほうの値のポインターを進めます。これで並べ替えた2つのリストをまとめ、共通の項目を見つけ、各レコードを別の並べ替えたリストの最も近いものに照合します。
大事な問いは、各ポインターが何を意味し、いつ動くかです。コードを書く前に、それをコメントに書き出してください。わざと確かめるべき特殊なケース:空のリスト、1つの項目、すべて等しい項目です。