概要

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

英語だと、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が直感に反するような気がするが、ペアを探すためのコードなので、配列内の値そのものではなくインデックスに注目してペアをカウントすれば良いため、このようなコードになる。

参照

• algodaily.com - The Two Pointer Technique
• www.geekforgeeks.org - Two Pointers Technique
• www.codingninjas.com - Two Pointer Approach
• jaigotec.com - [アルゴリズム(Ruby)]尺取り法の解説
• qiita.com - しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ
• na.fuis.u-fukui.ac.jp - しゃくとり法
• paiza.hatenablog.com - 【累積和、しゃくとり法】初級者でも解るアルゴリズム図解
• www.kumilog.net - 尺取り法
• scrapbox.io - しゃくとり法