JA
EnglishPortuguêsFrançaisDeutschTiếng ViệtEspañol한국어日本語简体中文
ホーム / 基礎 / アルゴリズム

Two Pointersとスライディングウィンドウ：配列と文字列最適化テクニック

Cris The Dev · 2026/10/05 · 7 分で読めます · 99

1. 概要

配列または文字列を走査する問題で、力ずくの解法がO(n²)またはO(n³)の複雑度になる場合、two pointersとsliding windowの2つのテクニックは通常、複雑度をO(n)に削減するのに役立ちます。この記事では、各テクニックの核となるアイデアを説明し、具体的なJavaの例を示します：ソート済み配列でのtwo sum、回文チェック、固定ウィンドウ内の最大部分和、および重複しない最長部分文字列。読み終わったら、パターンを認識して、同様の多くの問題に適用できるようになります。

2. Two Pointersとは

Two Pointersは、データ構造（通常はソート済み配列または文字列）上を移動する2つのインデックス変数（ポインタ）を使用するテクニックで、ネストされたループを避けるために使用します。2つのポインタは以下のように移動できます：

  • 同じ方向（fast/slow）：重複要素の削除、サイクル検出に使用。
  • 反対方向（両端からのleft/right）：合計がtargetと等しいペアの検索、回文チェックに使用。

2.1. 反対方向のTwo Pointers：合計がtargetと等しいペアを見つける

古典的な問題：昇順にソート済みの配列が与えられたとき、合計がtargetと等しい2つの数を見つけます。

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

解説：

  • leftは配列の始めから始まり、rightは配列の終わりから始まります。
  • sum < targetの場合、left側の数が小さすぎるため、より大きい数を取得するためにleftを増やします。
  • sum > targetの場合、right側の数が大きすぎるため、rightを減らします。
  • ループは最大n回実行されます。leftまたはrightが毎回1つのセルを移動するため、2層ループのO(n²)ではなくO(n)の複雑度になります。

JUnit 5 + AssertJでテストします：

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>
import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

注釈： このテクニックはソート済み配列が必須です。配列がまだソートされていない場合、事前にソートする必要があります（O(n log n)）か、HashMapを使用してソートなしでO(n)を保ちます。

2.2. 回文をチェックするTwo Pointers

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

2つのポインタが文字列の両端から始まり、文字を比較してから中央に進みます。異なる文字のペアが見つかった場合は、すぐにfalseを返します。全体を走査する必要はありません。このテクニックが文字列を反転してから比較する（reverse().equals()）より高速な理由は、中間のStringBuilderオブジェクト作成を避けられるためです。

3. スライディングウィンドウとは

スライディングウィンドウはTwo Pointersの変種で、連続した部分列（subarray/substring）に関連する問題に適用されます。各開始位置について最初から計算し直す代わりに、「ウィンドウ」[left, right]を保持し、ウィンドウがスライドするときに段階的に更新し、以前計算した結果を再利用します。

2種類あります：

  • 固定サイズウィンドウ：ウィンドウサイズが固定（例：k要素）。
  • 可変サイズウィンドウ：サイズが問題の条件に応じて変わる。

3.1. 固定サイズウィンドウ：サイズkの最大部分和

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

解説：

  • 最初のループは最初のウィンドウ（インデックス0からwindowSize - 1まで）の合計を計算します。
  • そこから、ウィンドウを右に1ステップずつシフトするたびに：新しい要素を追加し（numbers[right]）、ウィンドウを抜けたばかりの要素を引きます（numbers[right - windowSize]）。
  • これにより、各ステップはO(k)の合計を再計算する代わりにO(1)のみ必要になり、総複雑度はO(n)です。
import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // ウィンドウ [5, 1, 3]
    }
}

3.2. 可変サイズウィンドウ：重複文字のない最長部分文字列

この問題では、ウィンドウは「重複文字がない」という条件に応じて拡大縮小します。

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

解説：

  • rightは常に前進（ウィンドウを拡張）し、leftは現在のウィンドウ内に重複文字が見つかった場合にのみジャンプします。
  • lastSeenIndexは各文字の最後の出現位置を保存し、leftがどこにジャンプする必要があるかを判断します。
  • 条件lastSeenIndex.get(current) >= leftにより、その文字が現在のウィンドウ内にまだある場合にのみ「重複」と見なされ、leftが誤った方向に後退するのを防ぎます。
  • 各文字はrightで正確に1回処理されるため、総複雑度はO(n)です。
import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

"abcabcbb"でのデバッグ例：

right=0 'a' -> ウィンドウ="a"    長さ=1
right=1 'b' -> ウィンドウ="ab"   長さ=2
right=2 'c' -> ウィンドウ="abc"  長さ=3
right=3 'a' -> 重複、left=1 -> ウィンドウ="bca" 長さ=3
right=4 'b' -> 重複、left=2 -> ウィンドウ="cab" 長さ=3
...
maxLength = 3

4. 比較と各テクニックいつ使うか

状況 適切なテクニック
ソート済み配列、合計条件を満たすペア/トリプレットを見つける Two Pointers反対方向
対称性をチェック（回文）、配列をin-placeで反転 Two Pointers反対方向
ソート済み配列内の重複要素を削除 Two Pointers同じ方向（fast/slow）
サイズkの固定Subarray/substring Sliding window固定サイズ
動的条件を満たすSubarray/substring（重複なし、合計≤target…） Sliding window可変サイズ

共通点：両テクニックは既に処理した部分の再計算を避け、ポインタ/ウィンドウが移動するときに状態（sum、set、map）を保持することで、O(n²)からO(n)に削減します。

5. よくあるエラー

  • 終了条件left < rightを忘れ：left == rightのときに無限ループまたは要素と自身の比較が発生しやすい。
  • 未ソート配列にTwo Pointersを適用（事前ソートを忘れ）— 配列の単調性に基づいたポインタのインクリメント/デクリメントロジックが機能しないため、結果は完全に間違っている。
  • スライディングウィンドウでleftがシフトするときに状態更新を忘れ：例えばHashMap/sumから古い要素を削除し忘れ、ウィンドウがもはやウィンドウに属さないデータを「記憶」する。
  • ウィンドウの拡張/縮小条件を混同：可変サイズウィンドウでは、どの条件がrightを前進させるか、どの条件がleftを前進させるかを明確にする必要があります。逆にすると、ウィンドウは正しく縮小されません。

注釈： これらの2つのテクニックは、問題がすべての非連続部分集合を考慮する必要がある場合（例：subset sum）には適していません。その場合、バックトラッキングまたは動的計画法が必要であり、スライディングウィンドウではありません。

6. 結論

Two PointersとSliding Windowは、線形時間複雑度で配列と文字列の問題を解くための2つの基本的なツールです。パターンを認識する —ソート済み配列でペアを見つける必要があるか、または連続したsubarray/substringを最適化する必要がある—は、正しいテクニックを選択し、上記の例のように短くてテストしやすいコードを書くのに役立ちます。練習するときは、コードを書く前に、各ステップでleft/rightの状態を自分で描き直して、不変性を明確に理解してみてください。

algorithmsjavadata-structuresinterviewperformance
著者のアプリReflex Arena11 brain-speed games, live 1v1 duels, monthly seasonsiOS · Android

同じトピックの記事