最長連続部分列
最長連続部分列
このレッスンで分かること
setの「メンバーシップ判定O(1)」はhashmapと並ぶ重要パターン[100, 4, 200, 1, 3, 2]という配列が与えられたとき、1, 2, 3, 4という 連続する整数のシーケンス が含まれていて、その長さは4です- 関数
longestConsecutive(nums)は次を満たします
最長連続部分列 とは
整数配列を
setに入れて、連続する整数で最も長いシーケンスの長さをO(n)で求める。本レッスンでは、最長連続部分列 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
[100, 4, 200, 1, 3, 2] という配列が与えられたとき、1, 2, 3, 4 という 連続する整数のシーケンス が含まれていて、その長さは 4 です。並び順は問いません。これを 最長連続部分列 (Longest Consecutive Sequence) と呼びます。本レッスンでは set を使って O(n) で解く方法を学びます。
ソートすれば
O(n log n)で解けるが、setの「メンバーシップをO(1)で確認できる」性質を使えばO(n)まで落とせる。
仕様
関数 longestConsecutive(nums) は次を満たします。
- 整数配列
numsを受け取る (重複を含む可能性あり、未ソート) - 連続する整数で構成される最長のシーケンスの 長さ を返す
- 空配列なら
0を返す
例として nums = [100, 4, 200, 1, 3, 2] ならシーケンスは [1, 2, 3, 4] の長さ 4、nums = [9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6] ならシーケンスは [3, 4, 5, 6, 7, 8, 9] の長さ 7 です。
素朴な O(n log n) 解
ソートして隣同士を見るのが手っ取り早いです。
Python
def longestConsecutive(nums):
if not nums:
return 0
s = sorted(set(nums))
best = 1
cur = 1
for i in range(1, len(s)):
if s[i] == s[i-1] + 1:
cur += 1
best = max(best, cur)
else:
cur = 1
return bestソートで O(n log n)、走査で O(n)。シンプルだが速い解です。
O(n) アルゴリズム (set 活用)
もう一段速くするために set を使います。考え方は次の通りです。
- 配列全体を
setに入れる。重複が自動で消える - 各要素
vについて「v - 1がsetにない」ときだけ、vから右に向かってv + 1,v + 2, ... が含まれるか調べる
「左端のみ起点にする」ことで、長さ L のシーケンスがあっても L 回しか走査しません。全体としては各要素が高々 2 回しか触られないので O(n) です。
Python での実装
Python
def longestConsecutive(nums):
s = set(nums)
best = 0
for v in s:
if v - 1 in s:
continue
cur = 1
x = v
while x + 1 in s:
x += 1
cur += 1
if cur > best:
best = cur
return bestJavaScript での実装
JavaScript
function longestConsecutive(nums) {
const s = new Set(nums);
let best = 0;
for (const v of s) {
if (s.has(v - 1)) continue;
let cur = 1;
let x = v;
while (s.has(x + 1)) {
x += 1;
cur += 1;
}
if (cur > best) best = cur;
}
return best;
}Java での実装
Java
import java.util.*;
public class Solution {
public static int longestConsecutive(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int v : nums) s.add(v);
int best = 0;
for (int v : s) {
if (s.contains(v - 1)) continue;
int cur = 1;
int x = v;
while (s.contains(x + 1)) {
x++;
cur++;
}
if (cur > best) best = cur;
}
return best;
}
}Go での実装
Go
func longestConsecutive(nums []int) int {
s := map[int]bool{}
for _, v := range nums {
s[v] = true
}
best := 0
for v := range s {
if s[v-1] {
continue
}
cur := 1
x := v
for s[x+1] {
x++
cur++
}
if cur > best {
best = cur
}
}
return best
}よくある間違い
1 つ目は 起点判定を入れないこと。すべての v から右に伸ばそうとすると、シーケンスを何度も重複走査して O(n^2) に逆戻りします。「v - 1 が set にない要素だけ起点」が肝です。
2 つ目は 空配列の扱い。best = 0 で初期化しておけば自然に 0 を返します。best = 1 から始めると空配列で誤りになります。
3 つ目は 重複処理。set に入れる時点で重複は消えるので、配列に重複があってもバグりません。
setの「メンバーシップ判定O(1)」はhashmapと並ぶ重要パターン。O(n^2)をO(n)に落とす切り札になる。
やってみよう
[1, 2, 0, 1]を入力して答えが3になるか確認する (0, 1, 2で 3 個)。- 同じ問題を シーケンスそのもの (
[1, 2, 3, 4]を返す) に書き換えてみる。 - 並列で動かす場合に
setをどう分割するか考えてみる (実用的にはこちらが多い)。
最長連続部分列は
setの練習にちょうど良い問題。O(n)で解けると分かると爽快感がある。
よくある質問
Q. この内容は面接でよく聞かれますか？
A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。
Q. 計算量と空間計算量はどっちを優先しますか？
A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。
Q. 問題が解けないときどう取り組めば良いですか？
A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。
次のレッスン
次は 集合の積 (intersection) で、整数配列を set に入れて、連続する整数で最も長いシーケンスの長さを O(n) で求める を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 最長連続 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 最長連続 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
setを使ってO(n)(期待計算量) で解く- 重複や負の数が含まれていても正しく動作すること
- 空配列の場合は
0を返す
入出力例
test-cases.txt
longestConsecutive([100,4,200,1,3,2]) → 4
longestConsecutive([9,1,4,7,3,-1,0,5,8,-1,6]) → 7
longestConsecutive([1]) → 1
longestConsecutive([10,30,20]) → 1
longestConsecutive([0,3,7,2,5,8,4,6,0,1]) → 9
longestConsecutive([1,2,0,1]) → 3