java-two-pointer-technique

投稿日: 2019-10-19 2019-10-19
タグ: Java

Java 2ポインターテクニック

Java

1. 概要

このチュートリアルでは、配列とリストに関連する問題を解決するための2ポインターアプローチについて説明します。 *この手法は、アルゴリズムのパフォーマンスを改善するための簡単で効率的な方法です。*

2. テクニックの説明

配列またはリストに関する多くの問題では、配列の各要素を他の要素と比較して分析する必要があります。

このような問題を解決するには、通常、最初のインデックスから開始し、実装に応じて配列を1回以上ループします。 場合によっては、問題の要件に応じて一時配列も作成する必要があります。

上記のアプローチでは正しい結果が得られる可能性がありますが、スペースと時間の効率が最も良いソリューションは得られません。

その結果、多くの場合、_two-pointers approach_を使用して問題を効率的に解決できるかどうかを検討することをお勧めします。

2ポインターアプローチでは、ポインターは配列のインデックスを参照します。ポインターを使用することで、ループごとに1つの要素ではなく2つの要素を処理できます。*
```
2ポインターアプローチの一般的なパターンには、次のものが含まれます。
```
それぞれ開始と終了から開始する2つのポインター
両方を満たす

1つのポインターはゆっくりしたペースで動き、もう1つのポインターは
より速いペース

上記のパターンは両方とも、繰り返しの数を減らして、あまり使用しないで期待される結果が得られるため、問題のlink:/java-algorithm-complexity[*time and space complexity *]を減らすのに役立ちます。多くの追加スペース。

それでは、このテクニックをもう少しよく理解するのに役立ついくつかの例を見てみましょう。

3. 配列に合計が存在する

問題：整数のソートされた配列が与えられた場合、合計が特定の値に等しくなるような2つの数値があるかどうかを確認する必要があります。

たとえば、入力配列が_ [1、1、2、3、4、6、8、9] _で、ターゲット値が_11_の場合、メソッドは_true_を返す必要があります。 ただし、ターゲット値が_20_の場合、_false_を返す必要があります。

最初に、単純な解決策を見てみましょう。

public boolean twoSumSlow(int[] input, int targetValue) {

    for (int i = 0; i < input.length; i++) {
        for (int j = 1; j < input.length; j++) {
            if (input[i] + input[j] == targetValue) {
                return true;
            }
        }
    }
    return false;
}

上記のソリューションでは、入力配列を2回ループして、可能なすべての組み合わせを取得しました。 組み合わせの合計をターゲット値と照合し、一致する場合は_true_を返しました。 *このソリューションの時間の複雑さは__ *です

ここで、2ポインターテクニックをどのように適用できるかを見てみましょう。

public boolean twoSum(int[] input, int targetValue) {

    int pointerOne = 0;
    int pointerTwo = input.length - 1;

    while (pointerOne < pointerTwo) {
        int sum = input[pointerOne] + input[pointerTwo];

        if (sum == targetValue) {
            return true;
        } else if (sum < targetValue) {
            pointerOne++;
        } else {
            pointerTwo--;
        }
    }

    return false;
}

配列は既にソートされているため、2つのポインターを使用できます。 1つのポインターは配列の先頭から始まり、もう1つのポインターは配列の末尾から始まり、これらのポインターに値を追加します。 値の合計がターゲット値よりも小さい場合、左ポインターを増分し、合計がターゲット値よりも大きい場合、右ポインターを減分します。

ターゲット値と一致する合計を取得するか、配列の中央に到達し、組み合わせが見つからなくなるまで、これらのポインターを移動し続けます。 **このソリューションの時間の複雑さは__ **最初の実装よりも大幅に改善されています。

4. 配列の回転k _ステップ

問題：配列が与えられた場合、配列を_k_ stepsだけ右に回転させます。ここで_k_は負ではありません。 たとえば、入力配列が__ [1、2、3、4、5、6、7] _で、_k_が_4_の場合、出力は_ [4、5、6、7、1、2、3になります] _。

これを解決するには、2つのループを再度使用して時間の複雑さを_O（n ^ 2）_にするか、余分な一時配列を使用しますが、スペースの複雑さは_O（n）_になります。

代わりに2ポインター手法を使用してこれを解決しましょう。

public void rotate(int[] input, int step) {
    step %= input.length;
    reverse(input, 0, input.length - 1);
    reverse(input, 0, step - 1);
    reverse(input, step, input.length - 1);
}

private void reverse(int[] input, int start, int end) {
    while (start < end) {
        int temp = input[start];
        input[start] = input[end];
        input[end] = temp;
        start++;
        end--;
    }
}

上記のメソッドでは、入力配列のセクションをインプレースで複数回反転させて、必要な結果を取得します。 セクションを逆にするために、配列セクションの両端で要素の交換が行われる2ポインターアプローチを使用しました。

具体的には、まず配列のすべての要素を逆にします。 次に、最初の_k_要素を逆にして、残りの要素を逆にします。 *このソリューションの時間の複雑さは__ *です

5. _ LinkedListの中間要素_

問題：単一の_LinkedList_が与えられた場合、その中間要素を見つけます。 たとえば、input _LinkedList_が_1-> 2-> 3-> 4-> 5、_の場合、出力は_3_になります。

また、_LinkedList_のような配列に似た他のデータ構造で2ポインター手法を使用することもできます。

public <T> T findMiddle(MyNode<T> head) {
    MyNode<T> slowPointer = head;
    MyNode<T> fastPointer = head;

    while (fastPointer.next != null && fastPointer.next.next != null) {
        fastPointer = fastPointer.next.next;
        slowPointer = slowPointer.next;
    }
    return slowPointer.data;
}

このアプローチでは、2つのポインターを使用してリンクリストを走査します。 1つのポインターは1つ増え、もう1つのポインターは2つ増えます。 高速ポインタが最後に達すると、低速ポインタはリンクリストの中央になります。 *このソリューションの時間の複雑さは__ *です

6. 結論

この記事では、いくつかの例を見て、2ポインター手法をどのように適用できるかを説明し、アルゴリズムの効率をどのように改善するかを検討しました。

この記事のコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-3[Github上]で入手できます。

getdocs

9427