Skip to content

README.md

Latest commit

 

History

History
155 lines (103 loc) · 5.33 KB

README.md

File metadata and controls

155 lines (103 loc) · 5.33 KB

双方向ポインタ（Two Pointers）について詳しく解説

1. 双方向ポインタとは？

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

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

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

2. 基本的な考え方

2つのポインタをどう動かすか

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

3. 本題の「差が K 以下の整数ペアの数え方」

この問題では、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 になるまで繰り返す。

4. コードの詳細解説

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);

5. 具体的な動作を詳しく説明

入力例

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

処理の流れ

i j の初期値 j の最大位置 (j - i - 1) count の累計
0 (A[0] = 1) 0 3 (A[3] = 5) 3 - 0 - 1 = 2 2
1 (A[1] = 2) 3 3 (A[3] = 5) 3 - 1 - 1 = 1 3
2 (A[2] = 4) 3 4 (A[4] = 8) 4 - 2 - 1 = 1 4
3 (A[3] = 5) 4 4 (A[4] = 8) 4 - 3 - 1 = 0 4

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

6. 計算量の分析

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

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

7. まとめ

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

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

✅ この問題での適用方法

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

count += (j - i - 1); の処理について解説

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

具体的な動作

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

なぜ (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]

処理の流れ

i (固定) j の最大位置 (j - i - 1) カウント加算
i = 0 (A[0] = 1) j = 3 (A[3] = 5) 3 - 0 - 1 = 2 count += 2
i = 1 (A[1] = 2) j = 3 (A[3] = 5) 3 - 1 - 1 = 1 count += 1
i = 2 (A[2] = 4) j = 4 (A[4] = 8) 4 - 2 - 1 = 1 count += 1
i = 3 (A[3] = 5) j = 4 (A[4] = 8) 4 - 3 - 1 = 0 count += 0

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

まとめ

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