sko.kr

アルゴリズム - 3. Two Pointers（二つのポインタ）

algorithmstwo-pointersarraysstringsoptimization
By sko•9/28/2025•9 min read

Two Pointersを使うべきタイミング

Two Pointersは、異なる位置にある要素間の関係を体系的に探索する必要があるときに使用します。何らかの条件に基づいてポインタを移動させることで進行し、可能性を排除していくことができる場合に、このテクニックは機能します。

ソート済み配列が必要な問題

  • ターゲットを持つTwo Sum (クラシックなユースケース - どのポインタを動かすかを知るためにソートが必要)
  • Three Sum / Four Sum (ネストされたポインタペアを使用 - 除去のために順序付けが必要)
  • 特定の差を持つペアの検索 (領域を除去するために順序付けが必要)

未ソート配列で動作する問題

  • 最大の水を保持する容器 (インデックスが順序を提供し、値ではない)
  • 回文の検証 (両端からの自然な順序付け)
  • 配列/文字列の反転 (両端からスワップ)
  • パーティショニング問題 (オランダ国旗問題、クイックソートのパーティション)
  • 高速/低速ポインタのバリアント (サイクル検出、中間要素の検索)
  • 読み取り/書き込みポインタでの重複削除 (スキャン中に不変条件を維持)

例題（ソート済み配列）

ターゲット合計を持つペアの検索: ソート済み整数配列 [1, 3, 4, 6, 8, 9, 11] とターゲット合計 14 が与えられたとき、ターゲットに加算される2つの数を見つけます。

  • 位置0と6のポインタから開始: 1 + 11 = 12 (小さすぎる)
  • 左ポインタを位置1に移動: 3 + 11 = 14 (見つかった！)
  • 答え: インデックス [1, 6] の要素、つまり 3 と 11

ソートなしでは、O(n²)の比較が必要です。ソート済み配列でTwo Pointersを使用すると、O(n)時間で見つかります。

例題（未ソート配列）

最大の水を保持する容器: 高さ [1, 8, 6, 2, 5, 4, 8, 3, 7] が与えられたとき、x軸と共に最も多くの水を保持する容器を形成する2本の線を見つけます。

  • 位置0と8のポインタから開始: 面積 = 8 × min(1, 7) = 8
  • 左ポインタ（より小さい高さ）を位置1に移動: 面積 = 7 × min(8, 7) = 49
  • ポインタが出会うまで続け、最大面積を追跡
  • 答え: インデックス [1, 8] で面積49

ソートは不要です！インデックス自体が幅を提供し、より大きな面積を見つける可能性を持つために、より小さい高さのポインタを移動させます。

最も重要な洞察

Two Pointersは、各ポインタの移動によって不可能なオプションを排除しながら、解空間を体系的に探索します - ソート順序（合計問題の場合）または位置的制約（幾何学的問題の場合）を通じて、各比較は1つだけでなく、多くの可能性についての知識を与えてくれます。

メンタルノート: 「位置iで終わる最良の部分配列」に焦点を当てるKadaneのアルゴリズムやSliding Windowとは異なり、Two Pointersは異なる位置にある要素間の関係に焦点を当てています。あなたは特定の位置に固定されていません - 代わりに、比較に基づいて2つの独立したポインタを移動させることで、ペア/関係を探索しています。Kadaneが「この位置で拡張するか再開するか？」と尋ねるのに対し、Two Pointersは「より良い関係を見つけるためにどのポインタを移動させるべきか？」と尋ねます。

メンタルモデルの比較

  • Kadaneのアルゴリズム: 「位置iで終わる最良の部分配列は何か？」 - エンドポイントに固定
  • Sliding Window: 「位置iで終わる最良のウィンドウは何か？」 - 右境界に固定
  • Two Pointers: 「次に探索すべき2つの位置間の関係は何か？」 - アンカーなし、純粋な探索

位置的なアンカーリングの欠如がTwo Pointersをユニークにしています - 比較に基づいてどちらのポインタも自由に移動でき、解空間の全体領域を体系的に除去できます。

決定フレームワーク

ソート済み配列問題の場合（Two Sum）

  • 合計が大きすぎる？右ポインタを左に移動（合計を減少）
  • 合計が小さすぎる？左ポインタを右に移動（合計を増加）
  • 合計がターゲットと等しい？ペアを発見！

未ソート配列問題の場合（最大の水を保持する容器）

  • より小さい高さを指すポインタを移動
  • なぜ？より小さい高さが面積を制限するため、より高い線を探す
  • これまでに見た最大面積を追跡

コード例

ソート済み配列: Two Sum

function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const currentSum = nums[left] + nums[right];

    // DECISION FRAMEWORK
    if (currentSum > target) {
      // 合計が大きすぎる: 右ポインタを左に移動して減少
      right--;
    } else if (currentSum < target) {
      // 合計が小さすぎる: 左ポインタを右に移動して増加
      left++;
    } else {
      // ターゲット合計を見つけた
      return [left, right];
    }
  }

  return null; // 有効なペアが見つからない
}

// 問題からのデータを使用した例
const sortedArray = [1, 3, 4, 6, 8, 9, 11];
const targetSum = 14;
const result = twoSum(sortedArray, targetSum);
console.log(result); // [1, 6] - 3と11のインデックス

未ソート配列: 最大の水を保持する容器

function maxArea(heights: number[]): number {
  let left = 0;
  let right = heights.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(heights[left], heights[right]);
    const currentWater = width * minHeight;

    maxWater = Math.max(maxWater, currentWater);

    // DECISION FRAMEWORK
    if (heights[left] < heights[right]) {
      // 左壁が制限要因、より高い左壁を見つけようと試みる
      left++;
    } else {
      // 右壁が制限要因、より高い右壁を見つけようと試みる
      right--;
    }
  }

  return maxWater;
}

// 問題からの未ソート配列での使用例
const heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(heights)); // 49 (インデックス1と8の間)

未ソート配列: 回文チェック

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // DECISION FRAMEWORK
    if (s[left] !== s[right]) {
      return false; // 不一致を発見
    }
    left++;
    right--;
  }

  return true; // すべての文字が一致
}

// 任意の文字列で動作 - ソートは不要！
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false

ソート済み配列を超えて：Two Pointersがまだ機能する場合

一般的な誤解: 「Two Pointersはソート済み配列でのみ機能する。」

これは誤りです！Two Pointersは以下のことが可能な場合に機能します：

  1. 条件に基づいてポインタを移動することで体系的な進行を行う
  2. 可能性を排除するか、解空間を体系的に探索する
  3. 何らかの構造（必ずしもソート順序ではない）を使用して冗長な比較を回避する

なぜ最大の水を保持する容器は未ソート配列で機能するのか

重要な洞察: インデックス自体が必要な順序を提供します！

  • 幅は常に right - left（ポインタが収束するにつれて減少）
  • より小さい高さのポインタを移動させるのは、それが制限要因だから
  • 各移動は、より小さな幅だがより大きな高さの可能性がある容器を探索
  • 位置（値ではない）が幅を決定するため、ソートは不要

Two Pointersを可能にするさまざまな構造

  1. ソート済みの値 → 合計/差分問題の方向性のある決定を可能に
  2. 位置インデックス → 幾何学的問題の自然な順序付けを提供
  3. 文字列/配列の端 → 回文/反転問題の自然な境界
  4. 不変条件の維持 → インプレース変更用の読み取り/書き込みポインタ

「構造」はソート済みの値である必要はありません - 体系的な探索を可能にするだけで十分です！

疑問解消（ソート済み配列の場合）

一般的な疑問: 「アルゴリズムはターゲットとの比較に基づいてポインタを移動させますが、正しいペアをスキップしてしまったらどうなりますか？一度要素を通り過ぎたら、戻ることはありません - これでは解を見逃す可能性がありませんか？」

なぜこの考え方が間違っているのか

重要な気づき: すべてのポインタの移動は、不可能なペアのクラス全体を排除します！

  • 合計 < ターゲットの場合 → 左ポインタを右に移動 → 現在の左要素を含むすべてのペアを排除（すべて小さすぎる）
  • 合計 > ターゲットの場合 → 右ポインタを左に移動 → 現在の右要素を含むすべてのペアを排除（すべて大きすぎる）

実行中の体系的な探索

ターゲット 7 で [1, 3, 4, 6, 8] をトレースしましょう：

ステップ 1: left=0 (1), right=4 (8) → sum=9 > 7
         除去: 8と要素≥1のすべてのペア
         rightを3に移動

ステップ 2: left=0 (1), right=3 (6) → sum=7 = 7  → 発見！

ステップ1で何が起こったか注目してください：

  • 1+8=9をターゲット7と比較しました
  • 9 > 7なので、8と1、3、4、または6のペアはすべて≥9になることがわかります
  • したがって、8を完全に考慮から安全に除外できます

なぜ方向性のある移動が完全性を保証するのか

アルゴリズムはこの不変条件を維持します：

  • 通過した左要素を含むすべてのペアは完全に探索済み
  • 通過した右要素を含むすべてのペアは完全に探索済み
  • 残りの未探索空間は体系的に縮小し、最終的に空になる

保証: ソート順序により、単一の比較に基づいてどの領域全体が不可能かがわかるため、各ポインタの移動で多くのペアを排除できます。この体系的な探索により、すべての不可能なペアをスキップしながら、すべての実行可能なペアを正確に1回チェックすることが保証されます！

魔法はソート済み配列にあります：1つのペアとの比較を多くのペアに関する知識に変換し、O(n²)ではなくO(n)時間で解空間全体を探索できるようにします。

疑問解消（未ソート配列の場合）

一般的な疑問: 「Two Pointersはどうして未ソート配列で機能するのですか？どのポインタを移動させるかを知るためにソートが必要ではありませんか？」

なぜこの考え方が間違っているのか

重要な気づき: ソートは構造を作成する1つの方法にすぎません。利用可能な構造があれば、Two Pointersは機能します！

未ソート配列の場合、構造は以下から来ます：

  • 位置的関係 (最大の水を保持する容器: インデックスが幅を決定)
  • 自然な境界 (回文: 端から内側に向かって比較)
  • 維持される不変条件 (パーティショニング: ポインタの前の要素が条件を満たす)

最大の水を保持する容器 - なぜソートが不要なのか

高さ [1, 8, 6, 2, 5, 4, 8, 3, 7] を考えてみましょう。アルゴリズムが機能する理由：

  1. 幅はインデックスによって決定され、値ではない: 位置iとj間の距離は常に |i - j|
  2. ポインタの移動は常に幅を減少させる: これはインデックス位置によって保証される
  3. より高い線を期待してより短い線を移動させる: 幅が減少するため、より高い線だけがより大きな面積を与える可能性がある

重要な洞察: インデックス自体が必要な順序を提供します。ペアを見つけるために値を比較しているのではなく、値の順序に関係なく存在する位置的関係を使用しています。

なぜソートが実際に一部の問題を壊すのか

最大の水を保持する容器の場合、ソートは位置的関係を破壊します：

  • 元の配列: [1, 8, 6, 2, 5, 4, 8, 3, 7] - インデックスが重要
  • ソート済み: [1, 2, 3, 4, 5, 6, 7, 8, 8] - 元の位置が失われた！

問題は要素の元の位置に依存し、ソート順序ではありません。

覚えておくべき: Two Pointersには構造が必要で、必ずしもソート済みの値である必要はありません。特定の問題で体系的な探索を可能にする構造を特定してください。

バリエーションとパターン

高速と低速のポインタ（ウサギとカメ）

ポインタが異なる速度で移動する特別なバリアント：

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next; // 1ステップ移動
    fast = fast.next.next; // 2ステップ移動

    // DECISION FRAMEWORK
    if (slow === fast) {
      return true; // サイクル検出
    }
  }

  return false; // サイクルなし
}

インプレース変更のための読み取り/書き込みポインタ

このパターンは、配列をインプレースで変更するために、同じ方向に異なる速度で移動する2つのポインタを使用します：

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writePointer = 0; // 次の一意の要素を書き込む場所

  for (let readPointer = 1; readPointer < nums.length; readPointer++) {
    // DECISION FRAMEWORK
    if (nums[readPointer] !== nums[writePointer]) {
      writePointer++;
      nums[writePointer] = nums[readPointer];
    }
  }

  return writePointer + 1; // 一意の要素の長さ
}

// 例: [1,1,2,2,3] は [1,2,3,2,3] となり、長さ3

動作方法:

  • 読み取りポインタは、新しい一意の値を探して配列全体をスキャンします
  • 書き込みポインタは、次の一意の値を書き込む場所をマークします
  • 読み取りポインタが書き込みポインタの値と異なる値を見つけたとき：
    1. 書き込みポインタを前進させる
    2. 新しい一意の値を書き込み位置にコピー
  • 配列はインプレースで変更されます: [1,1,2,2,3] → [1,2,3,2,3]
    • 最初の3要素が一意の値になります: [1,2,3]
    • 残りの要素 [2,3] は無視されます（新しい長さを超えているため）
  • 3を返し、最初の3要素がすべての一意の値を含むことを示します

このパターンは、特定の要素を保持しながら他の要素を削除したいインプレース配列の変更に強力で、O(n)時間とO(1)空間で実行されます。

← Back to Blog