【Java】アルゴリズム徹底解説：指定値 `val` を配列から取り除く（Remove Element）

対象読者

• アルゴリズムを「動きのイメージ」で理解したい人
• 配列を in-place で安全に操作したい人
• Java で Two Pointer（2ポインタ）テクニックを身につけたい人

---

問題

配列 nums と整数 val が与えられる。配列の中から val を取り除き（実際には後方に追いやり）、
val ではない要素だけで構成される先頭区間の長さを返せ。
例：nums = [3,2,2,3], val = 3 → 戻り値 2（先頭2要素は [2,2]、残りは何でもよい）

---

問題の前提条件

• 配列 nums の要素型は int。

---

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

// 追加配列にval以外を詰めて戻す：メモリを余計に使う
public int removeElement(int[] nums, int val) {
    int[] temp = new int[nums.length];
    int index = 0;

    for (int num : nums) {
        if (num != val) {
            temp[index++] = num;
        }
    }
    for (int i = 0; i < index; i++) {
        nums[i] = temp[i];
    }
    return index;
}

何がいけないのか

• 追加配列 temp を使うため 空間計算量が O(n)。
• 配列コピーが複数回発生して無駄が多い。

---

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

発想：
**val ではない要素を左側に“圧縮”**していく。
**同時に逆にvalは右側へ追いやられる。
separator は「非 val の塊の右端」、runner は走査カーソル。
nums[runner] != val のたびに swap(nums, separator, runner) して separator++。
最終的に separator が 有効長（val 以外の要素数） になる。

class Solution {
    public int removeElement(int[] nums, int val) {
        // separator: 非val要素を前方に詰める位置
        // runner   : 配列を左→右へ走査するカーソル
        int separator = 0;
        int runner = 0;

        while (runner < nums.length) {
            if (nums[runner] != val) {
                swap(nums, separator, runner);
                separator++;             // 非val領域を1拡張
            }
            runner++;                    // 常に右へ進む
        }
        return separator;                // 非valの総数＝有効長
    }

    // 2要素を入れ替える補助メソッド
    private void swap(int[] nums, int i, int j) {
        if (i == j) return;              // 不要な自分自身スワップ回避（微最適化）
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

---

メンタルモデル（頭の中の動き方）

• separator は「非 val ゾーンの右端」を指す。
• runner は配列をスキャンし、非 val を見つけたら先頭側に押し固める。
• これを続けると、先頭から separator-1 までが “val を含まない有効区間” になる。

イメージ図（nums=[3,2,2,3], val=3）

初期: [3, 2, 2, 3]
        ^
      S,R

R=0 → 3==val → 何もしない / S=0
R=1 → 2!=val → swap(0,1) → [2,3,2,3], S=1
R=2 → 2!=val → swap(1,2) → [2,2,3,3], S=2
R=3 → 3==val → 何もしない / S=2

終了: S=2 → 先頭S個 [2,2] が有効

---

ステップトレース（丁寧版）

ステップ	runner	値	条件	処理	配列	separator
初期	0	3	== val	skip	[3,2,2,3]	0
1	1	2	!= val	swap(0,1)	[2,3,2,3]	1
2	2	2	!= val	swap(1,2)	[2,2,3,3]	2
3	3	3	== val	skip	[2,2,3,3]	2

最終戻り値：2（nums[0..1] が答えの区間）

---

計算量

• 時間計算量：O(n)（1回のリニアスキャン）
• 空間計算量：O(1)（定数メモリ）

---

まとめ

• 追加配列に逃げず、Two Pointer のメンタルモデルを見つけましょう。