二本指法（ツーポインタ）とスライディングウィンドウをわかりやすく解説

これらのテクニックが解決する問題

配列や文字列の問題の多くは、ペアや連続した範囲について問われます。合計が目標値になる2つの数、文字が重複しない最長の部分文字列、合計が k 以上になる最短の部分配列などです。すべてのペアやすべての範囲を調べると、コストは O(n²) 以上になります。二本指法では、ソート済みであることや、ウィンドウの更新が小さくて済むことといったデータの性質を利用して、多くの候補を一度に除外し、これを避けます。

両端のポインタ：ソート済み配列でのペアの和

ソート済みリスト [1, 3, 4, 6, 8, 11] から、和が 10 になる2つの数を探します。最小値と最大値から始めます。和が小さすぎるなら、増やす方法は left を右に動かすことだけです。大きすぎるなら right を左に動かします。

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

各ステップでポインタが1つ内側に動くため、ステップ数は最大でも n − 1 で、時間は O(n)、空間は O(1) です。同じ形で、文字列が回文かどうかの判定や配列のインプレース反転ができます。また、外側にループを重ねれば、3Sum を O(n³) ではなく O(n²) で解けます。

速いポインタと遅いポインタ：インプレースでの絞り込み

遅いポインタは次に残す要素を置く位置を示し、速いポインタはすべての要素を走査します。これで、追加のメモリなしにソート済みリストから重複を取り除けます。

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

連結リストでは、速いポインタが1ステップで2ノード、遅いポインタが1ノード進みます。2つが出会えば、リストにサイクルがあります（フロイドのサイクル検出法）。速いポインタが末尾に着いたとき、遅いポインタは中央にいます。

スライディングウィンドウ：重複のない最長の部分文字列

スライディングウィンドウは、範囲 s[left:right + 1] を常に有効な状態に保ちます。right を1文字ずつ前に進め、新しい文字がルールを破ったら、ウィンドウが再び有効になるまで left を進めます。その過程で最良のウィンドウを記録します。

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

ウィンドウには2種類あります。固定サイズ（k 要素）のウィンドウは、右から入る要素を加え、左から出る要素を引きます。たとえば移動平均の計算です。可変サイズのウィンドウは、上の例のように、条件を満たすように伸び縮みします。

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

時間計算量と空間計算量

while ループが入れ子になっていてもスライディングウィンドウが O(n) になる理由は、left と right がそれぞれ全体で最大 n 回しか前に進まないため、総作業量が最大でも 2n ステップだからです。

よくある間違い

• ソートされていないデータに両端ポインタを使う。left と right のどちらを動かすかという判断が正しいのは、配列がソートされているからこそです。
• 数値が負になりうるのに、和に基づくスライディングウィンドウを使う。ウィンドウを縮めても和が必ず減るとは限らなくなります。代わりに、累積和とハッシュマップを使ってください。
• ウィンドウ長の off-by-one。left..right を両端含みで数えると、要素数は right - left + 1 です。
• left < right で止めるのを忘れる。1つの要素が自分自身とペアになってしまいます。
• left を後ろに戻す。部分文字列の例では、last_seen[ch] >= left というチェックによって、古い位置に戻ってしまうのを防いでいます。

使うべき場面と、面接でよく出る問題

入力がソート済み（または安価にソートできる）でペアを探すとき、あるいは配列をインプレースで変更したいときは、二本指法を使いましょう。問題文に連続した部分配列や部分文字列とあり、ウィンドウの拡大に伴って予測どおりに変わる条件のもとで最長・最短・最大・個数を求めるときは、スライディングウィンドウを使います。データがソートされておらずペアを探す場合は、たいていハッシュセットのほうが簡単で、これも O(n) です。

• Two Sum II（ソート済み入力）、3Sum、Container With Most Water、Trapping Rain Water。
• Valid Palindrome、Reverse String、Move Zeroes、Remove Duplicates from Sorted Array。
• Longest Substring Without Repeating Characters、Minimum Window Substring、Sliding Window Maximum（deque を使用）。
• Linked List Cycle、Middle of the Linked List。

面接以外でも、同じ考え方は、ソート済みファイルのマージ、未確認応答パケットのウィンドウを管理するネットワークプロトコル（TCPのスライディングウィンドウ）、直近 N 秒間のイベントを数えるレートリミッター、時系列データの移動平均などに現れます。