概要

尺取り法についてまとめる。

英語だと、Two Pointer ApproachまたはTwo Pointer Techniqueと呼ばれる。

尺取り法とは

データセット（数列や文字列など）の右端と左端のインデックスを保持して、条件によって左右のインデックスを移動させることで、条件を満たすデータを探索するアルゴリズム。

特定の条件を満たすデータを区間の中から探索したいような時に役立つ。

例題

配列nの中から指定された数値m未満になる数字のペアがいくつあるかを求める関数を書く。

ex. n = [1, 3, -1, 2] m = 4 の場合、(1, -1）、（1, 2）、（3, -1）、（-1, 2）の4つのペアが該当するので4を返す。

関数を愚直に実装した場合のコードは次の通り。

func findPairs(n []int, m int) int {
    rslt := 0
    for i := 0; i < len(n); i++ {
        for j := i+1; j < len(n); j++ {
            if (n[i] + n[j]) < m {
                rslt++
            }
        }
    }
    return rslt
}

これだとO(N^2)の計算量になってしまうので、尺取り法を使ってO(N log N)にする。

func findPairs(n []int, m int) int {
    sort.Ints(n)
    cnt, l, r := 0, 0, len(n)-1
    for l < r {
        if n[l] + n[r] < m {
            cnt += r-l
            l++
            continue
        }
        r--
    }
    return cnt
}

左右のインデックスが重なり合うまで繰り返すことで、条件を満たすペアを全て探索できる。

ソートを行っているのは、効率的にペアを見つけやすいようにするためである。

r-lが直感に反するような気がするが、ペアを探すためのコードなので、配列内の値そのものではなくインデックスに注目してペアをカウントすれば良いため、このようなコードになる。

尺取り法について

概要

尺取り法とは

例題

参照