対象読者
- アルゴリズムについて学んでいる人
- いろんな問題に適用できる考え方を学びたい人
- Javaを学習中の人
問題の前提条件
- 受け取る配列の要素は
int型とする。
問題
配列の中に同じ要素があれば
trueを返し、なければfalseを返す関数を作成せよ。
解き方パターン1：Brute Force（よくない例）
まずは単純な実装を見てみる。
// 配列の中に重複する要素があれば true を返す
// 例: nums = [1,2,3,1] の場合、結果は true
public boolean containsDuplicate(int[] nums) {
// 特殊ケース: 要素数が1以下なら重複はないので false を返す
if (nums.length <= 1) return false;
// 配列をコピーして、2つの配列で二重ループを行う
int[] copiedNums = Arrays.copyOf(nums, nums.length);
for (int num : nums) {
for (int copiedNum : copiedNums) {
// 同じ要素が見つかれば true を返す
if (num == copiedNum) {
return true;
}
}
}
// 最後まで見つからなければ false を返す
return false;
}
何がいけないのか
この実装では、ネストされたループが問題になる。
要素数 n の配列に対して、各要素ごとに n 回の比較を行うため、計算量は O(n²) となる。
n × n = n²
入力サイズが増えると計算時間が指数的に増加するため、このようなアルゴリズムは避けたい。
では、どうすればよいか。次のパターンで最適化を考える。
解き方パターン2：HashMapを使った最適化例
コードの全体像
// 配列の中に重複する要素があれば true を返す
// 例: nums = [1,2,3,1] の場合、結果は true
public boolean containsDuplicate(int[] nums) {
// 特殊ケース: 要素数が1以下なら重複はないので false を返す
if (nums.length <= 1) return false;
// 要素の出現を記録するためのハッシュマップを作成
Map<Integer, Boolean> map = new HashMap<>();
// 配列を左から右へ一度だけ走査する
for (int num : nums) {
// すでに登録済みの要素であれば重複と判断し、true を返す
if (map.containsKey(num)) return true;
// 初めての要素であればマップに登録する
map.put(num, true);
}
// 最後まで重複が見つからなければ false を返す
return false;
}
このコードの良い点
-
for文が1回で済む（O(n))
配列numsを左から右へ一度だけリニアスキャンしており、ネストループがないため処理が高速。 -
HashMapを活用して探索を高速化
HashMapのキーアクセスは定数時間 O(1) で行える。
そのため、要素の存在確認を非常に効率的に行える。
リニアスキャンとは、配列要素をひとつずつ順にアクセスする操作を指す。
ロジックの詳細
-
配列
numsを左から右へ順に走査する。 -
各要素
numについて、mapにそのキーがすでに存在するか確認する。- 存在していれば重複あり →
trueを返す。 - 存在していなければ
map.put(num, true)で登録する。
- 存在していれば重複あり →
-
最後まで重複が見つからなければ
falseを返す。
途中で重複を検出した時点でループを終了できるため、無駄な計算を行わない点も優れている。
HashMapのアクセスがO(1)となる理由
HashMap は内部的にハッシュ関数を利用しており、キーから格納位置（インデックス）を直接計算する。
そのため、配列のように線形探索する必要がなく、平均的には定数時間でアクセスできる。
このように、
- 要素の存在確認 (
containsKey) - 追加 (
put)
の両方が O(1) で完結する。
この「定数時間アクセス」の考え方は、多くのアルゴリズム最適化に応用できる重要な基礎である。
参考:
まとめ
- ネストループによる O(n²) の実装は避けよう（計算量を意識しよう）。
- １回のリニアスキャンとHashMapを利用すれば メソッドとしてO(n) での実装が可能。
- ハッシュアクセスのO(1)という考え方は、他の問題にも応用できる。
個人的に思うこと
AI支援によるコード生成（バイブコーディング）を行う際でも、
このような基本的なアルゴリズムの定石や最適化パターンを理解しておくことは重要だと感じる。
まぁAIに「最適化して」と指示すればある程度は改善されるが、
パフォーマンスや責任が伴う箇所では、自分自身で判断できる知識が必要になる。