双方向ポインタ（Two Pointers） とは、配列の異なる位置にある2つのポインタ（変数 i と j など）を使い、データを効率的に探索するアルゴリズムの手法です。

この手法は ソート済みのデータに対して特に有効 で、以下のような問題で使われます：

• 特定の条件を満たすペアを数える
• 2つの数の和が特定の値になるかを判定する
• 区間の合計や条件を満たす部分列を探索する

1. ポインタ i（左側）を固定し、ポインタ j（右側）を動かす
   • 例えば、A[i] を固定して、A[j] を条件を満たす最大の位置まで動かす。
2. 条件を満たさなくなったら i を動かす
   • A[j] - A[i] > K になったら i を進める。

この問題では、A[j] - A[i] <= K を満たすペア (A[i], A[j]) の数を求めます。

1. i と j の2つのポインタを用意（i=0 からスタート、j も 0 からスタート）。
2. j を右に動かし、A[j] - A[i] <= K を満たす最大の j を見つける。
3. そのとき A[i] と組み合わせられるのは A[i+1] から A[j-1] までの (j - i - 1) 個。
4. i を1つ進めて再計算する。
5. i が N-1 になるまで繰り返す。

function countPairsTwoPointers(N, K, A) {
    let count = 0;
    let j = 0; // jはiとともに進めるポインタ

    for (let i = 0; i < N; i++) {
        while (j < N && A[j] - A[i] <= K) {
            j++; // 条件を満たす限り j を進める
        }
        count += j - i - 1; // (j - i - 1) 個のペアが作れる
    }

    console.log(count);
}

// 入力例
const [N, K, ...A] = `5 3
1 2 4 5 8`
    .split(/\s+/)
    .map(Number);
countPairsTwoPointers(N, K, A);

N = 5, K = 3
A = [1, 2, 4, 5, 8]

最終的に、ペア数は 4 となります。

• i は N 回ループする。
• j も N 回以内に右端まで進む。
• 合計 O(N) で解ける。

これは 二分探索（O(N log N)）よりも高速 で、大きな N（最大 100000）でも高速に動作します。

✅ 双方向ポインタ（Two Pointers）とは？

• 2つのポインタを使って効率的に探索 するアルゴリズム。
• ソート済みデータ に適用すると O(N) で高速に解ける。

✅ この問題での適用方法

• i を固定し、j を動かして A[j] - A[i] <= K を満たす最大の j を見つける。
• A[i] と組み合わせられるのは (j - i - 1) 個。
• O(N) の時間計算量 で解ける。

この部分は、A[i] を固定したときに、差が K 以下となる A[j] の個数を数える処理 です。

1. i を左ポインタとして 0 から順に動かす
2. j を右ポインタとして A[j] - A[i] <= K を満たす間、右に進める
3. j が条件を満たさなくなったら、その j までに作れるペア数 (j - i - 1) を加算する

• j - i ではなく j - i - 1 になっている理由は、A[j] は条件を満たさない j の位置にあるため、カウントしないようにするためです。
• A[i] と組み合わせる相手は A[i+1] から A[j-1] まで なので、j-1 - i を求めるために -1 している。

N = 5, K = 3
A = [1, 2, 4, 5, 8]

最終的に count = 4 となります。

1. j は A[j] - A[i] <= K を満たす最大の位置まで進める
2. i 固定時に、A[i+1] から A[j-1] までの (j - i - 1) 個 のペアが作れる
3. 計算量は O(N)