← 5주차 · 해시: 맵과 셋
어려움해시배열

가장 긴 연속 수열

정수 배열 nums가 주어져요. 값이 연속으로 이어지는 부분수열 중 가장 긴 것의 길이를 반환해요. 원래 배열에서의 순서는 상관없고, 중복된 값은 한 번만 세요.

정렬하면 O(n log n)에 쉽게 풀려요. 여기서는 셋만으로 `O(n)`에 푸는 게 목표예요.

핵심은 어디서부터 세기 시작할지 고르는 거예요. 모든 값에서 시작해 세면 같은 구간을 몇 번씩 다시 세지만, x - 1이 셋에 없는 값 — 즉 구간의 시작점에서만 세면 각 값을 정확히 한 번씩만 방문해요.

예시

예시 1
입력
nums = [100, 4, 200, 1, 3, 2]
출력
4
설명
1, 2, 3, 4 가 이어지니까 길이 4 예요.
예시 2
입력
nums = [1, 1, 1]
출력
1
설명
중복은 한 번만 세요.
예시 3
입력
nums = [10]
출력
1

제한 사항

  • 1 ≤ nums.length ≤ 100,000
  • -10^9 ≤ nums[i] ≤ 10^9
값을 전부 셋에 넣고, 셋을 돌면서 x - 1이 셋에 없는 값에서만 x + 1, x + 2, ... 로 세어 나가요. 안쪽 반복문이 있어도 전체는 O(n)이에요 — 각 값은 자기가 속한 구간에서 딱 한 번만 세어지거든요.
javascript
function longestConsecutive(nums) {
  const seen = new Set(nums);
  let best = 0;
  for (const n of seen) {
    if (seen.has(n - 1)) continue;
    let length = 1;
    while (seen.has(n + length)) length++;
    if (length > best) best = length;
  }
  return best;
}
이전 문제두 수의 합
다음 문제완주하지 못한 선수
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.