双指針（Two Pointers）パターン

基本

カテゴリ: binary-search

概要

双指針パターンは、2つのポインタ（インデックス）を使用して配列やリストを効率的に操作するテクニックです。通常、ポインタは配列の両端から始めて中央に向かって移動するか、同じ方向に異なる速度で移動します。このパターンを使用すると、二重ループ（O(n²)）を使わずに、線形時間（O(n)）で問題を解決できることが多いです。

コードテンプレート

Java

Python

- 両端から中央へ
int left = 0;
int right = array.length - 1;
while (left < right) {
    // 条件に応じてポインタを移動
    if (条件) {
        left++;
    } else {
        right--;
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

ソート済み配列ペアを見つける和が特定の値回文部分配列最大の面積最短の距離二重ループを避けるインデックスのペア左右から操作ソートされた入力二つの要素対称性前後から読む配列の両端

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
二数の和 II（Two Sum II）: ソート済み配列で、2つの要素の和が目標値と等しくなるようなインデックスのペアを見つける
2
コンテナに最も多くの水を入れる（Container With Most Water）: 最大の面積を持つコンテナを見つける
3
回文判定（Valid Palindrome）: 文字列が回文かどうかを判定する
4
三数の和（3Sum）: 配列内の3つの要素の和がゼロになるような組み合わせを見つける

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

最大の水容器

n個の非負整数 a1, a2, ..., an が与えられ、各数値は座標 (i, ai) を表します。n本の垂直な線が x = 1, x = 2, ..., x = n の位置に引かれ、それぞれの高さ...

中

3数の和

整数の配列 nums が与えられたとき、和が 0 になる 3 つの要素 nums[i], nums[j], nums[k] のすべての組み合わせを見つけてください。ただし、i != j, i != k...

易

ソート済み配列から重複を削除

整数の昇順にソートされた配列 nums が与えられたとき、各要素が一度だけ現れるように重複を削除し、相対的な順序を保持してください。配列の最初の部分に結果を配置し、結果の長さ k を返してください...