DSA の 2 ポインター パターン

こんにちは！ DSA の 2 ポインタ テクニックと呼ばれるこの素晴らしいトリックについてお話しましょう。心配しないでください。楽しみを保ち、定着させるためにいくつかのビジュアルを追加します。始める準備はできましたか?

それで、この 2 つのポイントは何ですか?

これは、フィールド (配列) の異なる側から開始する 2 人のプレーヤー (ポインターと呼びます) がいるゲームのようなものだと考えてください。次のいずれかを行うことができます:

1. お互いに向かって走ります (ちょっとロマンチックですね?)
2. 同じ方向に向かって競争する (競争力を高める!)
3. 自分のことをやりましょう (フリースタイル モード)

このテクニックは、大量のループを作成することなく、大量の問題を非常に効率的に解決するのに役立ちます。なかなかいいですね?

なぜそれを気にする必要があるのですか?

そうですね、これはコードにとってスーパーパワーのようなものです:

• 高速です: O(n²) ではなく O(n) で問題を解決します。コードがズームします!
• シンプルです: 行が少なく、理解しやすいです。
• 柔軟です: 配列、文字列、さらにはリンクされたリストでも動作します!

いくつかのタイプの 2 点問題を見てみましょう

1. 互いに向かって移動するポインタ

ソートされた配列内で合計が目標となる 2 つの数値を見つけようとしていると想像してください。それは、二人が真ん中で出会うためにお互いに向かって走っているようなものです。

これは JavaScript の簡単な例です:

function twoSumSorted(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return -1; // No pair found
}

console.log(twoSumSorted([1, 2, 3, 4, 6], 10)); // Output: [2, 4]

数字が並んだかわいい小さな文字であると想像してください:
① ② ③ ④ ⑤

• 左ポインタは①から始まります
• 右ポインタは⑤から始まります
• 彼らは、完璧な相手を見つけるためにゆっくりとお互いに近づいていきます

2.これは、文字列が回文であるかどうかを確認するのに最適です。 2 人の友人が単語の末尾から始めて、単語の中央に向かって移動し、すべてが一致した場合にハイタッチする様子を想像してください。

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

    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }

    return true;
}

console.log(isPalindrome("racecar")); // Output: true
console.log(isPalindrome("hello"));   // Output: false

2 匹のアリが「レースカー」という単語の上で互いに向かって這っているところを想像してください:
r<-> r ?
<-> ?
c <-> c ?

回文が確認されました! ?

このテクニックの素晴らしい応用例:

1. 目標金額を見つける (上記と同様)
2. ソートされた 2 つの配列をマージする
3. 閉じ込められた雨水の計算 (これをググってみてください。興味深いです!)
4. リンクされたリストを逆にする

プロのヒント:

• 最初に分類すると、これらの問題がはるかに簡単になります
• 特殊なケース (空の配列、重複、極端な値) に注意してください
• スケッチしてみよう!配列または文字列を描画すると、バグを回避できます

レベルアップしたいですか?次のチャレンジに挑戦してください:

1. Two Sum II - 入力配列がソートされている (LeetCode 167)
2. 繰り返し文字を含まない最長の部分文字列 (LeetCode 3)
3. 有効な回文 (LeetCode 125)
4. 雨水をトラップする (LeetCode 42) - 冒険したいなら!

ツーポイントテクニックは、コーディングにおけるスイスアーミーナイフのようなものです。シンプルですが強力なので、少し練習すれば、何も考えずに使えるようになります。

質問がありますか、それとも解決策を共有したいですか?コメントをドロップするか、私に声をかけてください。コーディングを楽しんでください!

以上がDSA の 2 ポインター パターンの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。