2つのポインタ法

2.1 2つのポインタ法の定義

2つのポインタ法は、配列や文字列のさまざまな問題を解決するために使われるテクニックで、2つのポインタ（インデックス）を使ってデータを特定のルールに従って移動させる方法だよ。この方法を使うと、指定された条件を満たす要素のペアや部分集合を見つける問題を効率的に解決できるんだ。

この方法では、通常データ構造の反対の端にポインタを初期化して、お互いに向かって移動させるか、特定のルールに従って移動させるようにするよ。2つのポインタ法を使うと、より素朴なアプローチと比べて、アルゴリズムの時間計算量をかなり減らせるんだ。

基本原則

1. 2つのポインタの初期化: ポインタは配列や文字列の先頭と末尾にセットされるか、問題に応じて異なるインデックスにセットされるよ。
2. ポインタの移動: ポインタは特定のルールに従って移動される（例: 両方のポインタが中央に向かって動く、または片方が動いてもう片方がそのままになる）。
3. 条件のチェック: 各ステップで、ポインタをさらに移動させるか、アルゴリズムを終了するかを決定する条件をチェックするよ。

時間計算量:

O(n) — 大半のケースでは、両方のポインタが配列を1回または複数回通過するけど、合計でO(n)を超えることはないよ。

いくつかの問題では、条件やポインタの初期位置に依存して、時間計算量がO(n log n)やO(n^2)になることもあるけど、それはレアケースだよ。

2つのポインタ法で解決できる問題の例:

2.2 指定された数の合計になる2つの数を配列から探す

問題:

解決策:

配列の先頭に1つのポインタ、末尾にもう1つのポインタを初期化して、ポインタが指す要素の合計をチェックするよ:

• もし合計がtargetと等しいなら、インデックスを返す。
• もし合計がtargetより小さいなら、左のポインタを右に動かす。
• もし合計がtargetより大きいなら、右のポインタを左に動かす。

時間計算量: O(n).

Pythonでのコード例:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 パリンドロームのチェック

問題:

文字列がパリンドロームかどうかをチェックする。

解決策:

文字列の先頭と末尾にポインタを初期化して、ポインタが指す文字を比較するよ:

• もし文字が等しいなら、両方のポインタをお互いに向けて動かす。
• もし文字が等しくないなら、その文字列はパリンドロームではない。

時間計算量: O(n).

Pythonでのコード例:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

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

問題:

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

解決策:

2つのポインタを使って、1つは結果の配列の現在の位置を、もう1つはすべての要素を走査するようにするよ:

• もし現在の要素が前の要素と等しくないなら、それを結果の配列に書き込む。

時間計算量: O(n).

Pythonでのコード例:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index