集合で並べ替えずに 1 ずつ続く数の最長を求める

配列とハッシュ問題 99

ばらばらに並んだ整数から、1 ずつ続いて並べられる数の、いちばん長い続きの長さを求めます。値を集合に入れ、続きの先頭の数からだけ数えて O(n) にする、ハッシュの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

ある人が勉強会に来た日の番号を、整数の並び nums で受け取ります。並びは来た順ではなく、ばらばらです。同じ日の番号が 2 回以上入っていることもあります。

番号が 1 ずつ続いた日の組 (たとえば 7、8、9) のうち、いちばん長い物の日数を返す関数を書いてください。

並びの中の位置は関係ありません。値だけを見て、1 ずつ続いているかを考えます
同じ番号は 1 日として数えます
nums が空なら 0 を返します
nums の長さは 0 以上 100000 以下で、値は -1000000000 以上 1000000000 以下です
並べ替えを使わず、時間が O(n) の書き方にしてください

入力と出力の例

例 1

2、3、4 の 3 日と、10、11、12、13 の 4 日の 2 つの続きがあります。長いのは 4 日の方です。

nums = [12, 3, 11, 4, 13, 2, 10]

例 2

5 と 7 が 2 回ずつ入っていますが、1 日と数えます。5、6、7、8 の 4 日です。

nums = [5, 5, 6, 8, 7, 7]

例 3

空の並びです。

nums = []

面接での聞かれ方

面接では、並べ替えを禁じる形で渡されることがよくあります。

「並べ替えずに、O(n) で最長の連続した数の長さを求めてください」
「同じ数は入りますか？」と、自分から確かめるかを見られます
先に並べ替えの答えを言わせてから、「O(n) にできますか？」と詰められることもあります

並べ替えなら O(n log n) ですぐ書けるので、まずそれを口に出してから、O(n) へ縮める道筋を話すと伝わりやすくなります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「ハッシュマップ」に、この型の要点を表とコードでまとめています。

ハッシュは、値から番地を計算して、探す手間をほぼ 1 回にする仕組みです。重複や回数の問題は、この形で解けます。

まず考える手順

段 1

素直に書くなら、並べ替えてから前から読み、1 つ前より 1 大きければ続きを伸ばし、同じ値なら読み飛ばし、それ以外なら続きを 1 から数え直します。正しく動きますが、並べ替えに O(n log n) かかり、問いの決まりに合いません。

段 2

値を集合に入れれば、「x + 1 はあるか」を一定の手間で調べられます。そこで、どの値 x からも x + 1、x + 2 と集合をたどれば、x から始まる続きの長さが分かります。ただし、全部の値から数えると、続きの中の値ごとに同じ道を何度もたどり、長い続きでは O(n²) になります。

段 3

数え始めるのを、続きの先頭だけにします。x - 1 が集合に無い x が先頭です。例 1 なら 2 と 10 だけから数えます。先頭からだけ伸ばすので、どの値も、たどられるのは自分の続きの先頭から 1 回だけです。

段 4

繰り返しは、元の並びではなく集合の方で回します。元の並びで回すと、同じ先頭の値が何回も入っているとき (たとえば 1 が 5 万回と、1 から 5 万まで)、同じ長い道を何回もたどってしまいます。

解答

Python

def longest_streak(nums):
    have = set(nums)
    best = 0
    for x in have:
        if x - 1 in have:
            continue
        y = x
        while y + 1 in have:
            y += 1
        size = y - x + 1
        best = max(best, size)
    return best

JavaScript

function longestStreak(
  nums
) {
  const have = new Set(nums);
  let best = 0;
  for (const x of have) {
    if (have.has(x - 1)) {
      continue;
    }
    let y = x;
    while (have.has(y + 1)) {
      y++;
    }
    const size = y - x + 1;
    best = Math.max(best, size);
  }
  return best;
}

Go

func longestStreak(
	nums []int,
) int {
	have := map[int]bool{}
	for _, x := range nums {
		have[x] = true
	}
	best := 0
	for x := range have {
		if have[x-1] {
			continue
		}
		y := x
		for have[y+1] {
			y++
		}
		best = max(best, y-x+1)
	}
	return best
}

x - 1 が集合にあれば、x は続きの途中なので飛ばします。先頭の x からだけ y を伸ばし、続きの最後の値 y が分かったら、長さは y - x + 1 です。Go には集合の型が無いので、値から true への map で代わりにしています。無い鍵は false と読めます。

計算量

時間は O(n) です。集合を作るのに O(n)、どの値も「先頭か」の確かめで 1 回、続きをたどるので 1 回見られるだけです
使う記憶は O(n) です。集合に、違う値の数だけ入ります
段 1 の並べ替えの書き方は、時間が O(n log n) です。全部の値から数える書き方は、続きが長いと O(n²) です

よくある間違い

先頭かどうかを確かめずに、全部の値から数える。答えは合いますが、1 から 10 万までのような長い続きで、たどる回数が O(n²) になります。x - 1 が無い値からだけ数えます
元の並びで繰り返す。同じ先頭の値がたくさん入っていると、同じ続きを何回もたどります。集合の方で回します
並べ替えたあと、同じ値で続きを切る。例 2 で 5、5 のところで数え直すと、4 ではなく 3 を返します。同じ値は読み飛ばします
空の並びで、best を 1 から始める。例 3 で 1 を返します。0 から始めます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def longest_streak(nums: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(longest_streak([12, 3, 11, 4, 13, 2, 10]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します