しゃくとり法という競プロのテクニックがあります。 英語ではTwo-Pointer Techiniqueといいます。 これがなぜ有効かを図を使って説明します。 断っておきますが、内容の正しさは保証しません。

しゃくとり法というのはこんな問題の時に使えるアルゴリズムです。

（問題）長さNの正の整数列があります。このうち、 和が10以下の部分列のうち、最長のものを見つけよ。

このアルゴリズムはO(N^2)で全列挙すれば解けますが、Nが大きい時には困ります。 そこでこの問題を探索領域を狭めてO(N)で解けるようにするのがしゃくとり法です。

計算量を減らす時には、なんらか問題の制約を利用します。 それによって、以前に計算した値を再利用したり、探索領域を限定したりします。

この問題では例えば、長さ3の[3,6)という領域で和が和が10以下であることがわかるならば、 長さ2の[4,6)という領域について考えることは無意味です。 なぜならば、明らかに10以下ですし、長さは3より短いからです。

このアイデアに基づいて、しゃくとり虫を配列の上で動かしていくのがしゃくとり法です。 直感的には、そりゃそうだろうと言えます。

では、なぜこのアルゴリズムがO(N)に落とせるのか、 さらに、計算量を落とすためにはどういう制約が必要なのかを図を使って考えます。

まず、上の問題でいうと、和が10以下となる[L,R)の組み合わせを全列挙したとしましょう。 それをTで表します。右上の領域は便宜的にFであるとしましょう。

すると、このうち探索しなければいけないのは 赤で塗りつぶした領域だけとわかります。 だから、計算量はO(N)に落ちます。

この図では、しゃくとり法は、「頭を伸ばしていき、Fにぶつかったらしっぽを1つ縮める」を繰り返して いくアルゴリズムだといえます。 当然、f(L,R)が定義出来るならば、このアルゴリズムをフレームワーク化することも出来ます。 例えば、上の問題であれば最初にO(N)を払って累積和を計算すればよいです。

ここでは、ある条件（ここでいうと和は10以下）に対して単調性が求められます。 つまり、Tを続けていって一度Fに当たったら、その先にはTは存在しないことが求められます。 そのために、「正の」整数列であることが条件として必要になります。 また、仮に最長の代わりに最短と問題と書き換えた場合も、使えなくなります。

あくまでも、図に示した赤の領域を探索した場合に網羅的に探索してると言える問題にしか使えない 制約の厳しいアルゴリズムなのです。