【Java】アルゴリズム徹底解説：配列内の0を末尾に移動する良い方法・悪い方法（Two Pointerで可視化）

対象読者

• アルゴリズムを 「動きのイメージ」 で理解したい人
• 配列操作を 効率的かつ視覚的 に理解したい人
• JavaでTwo Pointer（2ポインタ）テクニックを学びたい人

---

問題

配列の中に含まれるすべての0を、他の要素の順序を保ったまま末尾に移動せよ。

例：
nums = [0,1,0,3,12] → 結果：[1,3,12,0,0]

---

問題の前提条件

• 配列 nums の要素型は int。

---

解き方パターン1：Brute Force（よくない例）

// 配列内の0を末尾に移動する（非効率な例）
public void moveZeroes(int[] nums) {
    // 0以外の要素を一時的に保持する配列を用意
    int[] temp = new int[nums.length];
    int index = 0;

    // 0以外の要素をtempに順番に詰める
    for (int num : nums) {
        if (num != 0) {
            temp[index++] = num;
        }
    }

    // tempからnumsへ戻す
    for (int i = 0; i < nums.length; i++) {
        nums[i] = (i < index) ? temp[i] : 0;
    }
}

---

何がいけないのか

• 新しい配列 temp を作っているため、空間計算量が O(n)。
• 配列を2回走査しており、処理効率も悪い。
• **「in-placeでやりたい」**という要件（余計なメモリを使わない）を満たせていない。

---

解き方パターン2：Two Pointer（良い例）

発想：
0でない値を左に“圧縮”していくように動かす。
結果的に、押し出された空き（右端）に0が集まる。

class Solution {
    public void moveZeroes(int[] nums) {
        // separator: 「非ゼロの要素を詰めていく位置」
        // runner: 「探索カーソル」非ゼロを見つける役割
        int separator = 0;
        int runner = 0;

        // 配列を1回だけ走査（拡張for文でより読みやすく）
        while (runner < nums.length) {
            // 非ゼロを見つけたら前に詰める
            if (num != 0) {
                nums[separator] = num;  // 非ゼロを左詰め
                separator++;
            }
            runner++;
        }

        // 残りを0で埋める
        while (separator < nums.length) {
            nums[separator++] = 0;
        }
    }
}

---

このコードの良い点

• 空間計算量O(1)：配列そのものを直接操作する。
• 時間計算量O(n)：配列を一度走査するだけ。
• 安定性が保たれる：非ゼロの出現順序が壊れない。
• コードの意図が明確で、メンタルモデルと一致している。

---

メンタルモデル（動きのイメージ）

イメージとしては、
「非ゼロを左側へ順に詰めていく」という圧縮操作。

初期: [0, 1, 0, 3, 12]
        ^
      S,R

runnerが1(非ゼロ)を見つける → nums[0] = 1
[1, 1, 0, 3, 12]
   ^
  S,R

runnerが3(非ゼロ)を見つける → nums[1] = 3
[1, 3, 0, 3, 12]
      ^
     S,R

runnerが12(非ゼロ)を見つける → nums[2] = 12
[1, 3, 12, 3, 12]
         ^
        S,R

→ 最後に separator より右をすべて0で埋める
[1, 3, 12, 0, 0]

---

実行例（ステップごとに確認）

例1：nums = [0,1,0,3,12]

1. separator=0
   → runner=0: 0 → skip
   → runner=1: 1 → nums[0]=1, separator=1
   → runner=3: 3 → nums[1]=3, separator=2
   → runner=4: 12 → nums[2]=12, separator=3
2. 残り [3,4] を 0 で埋める → [1,3,12,0,0]

---

例2：nums = [1,0,0,0,1]

1. runner=0: 1 → nums[0]=1, separator=1
2. runner=4: 1 → nums[1]=1, separator=2
3. 残りを0埋め → [1,1,0,0,0]

✅ 補足：以前の僕が書いた実装（runner=1開始）では [1,0,0,0,1] のまま変化しない不具合があったが、
今回の修正版ではすべてのケースで正常動作する。
runnerも0スタートであるべき

---

エッジケースも全てOK

入力	出力	説明
[0,0,0]	[0,0,0]	全て0でもOK
[1,2,3]	[1,2,3]	非ゼロのみでも順序保持
[0,1]	[1,0]	シンプルな押し出し
[1,0,0,0,1]	[1,1,0,0,0]	先頭非ゼロでも正しく圧縮

---

なぜこの方法が速いのか

1. ループが1回で済む（非ゼロ圧縮）
2. 追加メモリを使わない（in-place処理）
3. 無駄なswapがない（値の書き換えだけ）

この3つが揃うことで、
時間O(n) × 空間O(1) という最適構造になります。

---

まとめ

• Brute Force法：O(n)空間を使い、配列を2回操作
• Two Pointer法：O(1)空間で配列を1回走査
• ポイントは 「非ゼロを左詰め」→「残りを0埋め」 の2ステップ構造。