Funcia
Lv.2arrayhashsliding-windowtwo-pointers

같은 값이 없는 가장 긴 구간

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

놀이공원 퍼레이드에 참가한 차량 NN대가 한 줄로 지나가고, i번째 차량에는 캐릭터 번호 nums[i]가 붙어 있습니다. 사진가는 연속으로 지나가는 차량들을 한 장에 담으려 하는데, 같은 캐릭터가 두 번 찍히면 안 됩니다.

같은 값이 두 번 이상 나오지 않는 가장 긴 연속 구간(연속 부분 배열)의 길이를 반환하세요.

입출력 예

numsresult
[1, 2, 1, 3, 4, 3]4
[5, 5, 5]1
[7, 3, 9, 1]4

입출력 예 설명

예 1 — [2, 1, 3, 4]가 가장 깁니다. 여기서 한 칸만 늘려도 1 또는 3이 겹칩니다.

예 2 — 모든 값이 같으므로 한 대씩만 찍을 수 있습니다.

예 3 — 모든 값이 서로 다르므로 전체를 찍을 수 있습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → int

제한 사항

  • 1≤N=1 \le N = nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

nums기대 출력
[1,2,1,3,4,3]4
[5,5,5]1
[7,3,9,1]4

힌트

힌트

오른쪽 끝 r을 한 칸씩 늘려 가면서, 구간의 왼쪽 끝 l은 뒤로 가지 않게 관리하세요(슬라이딩 윈도우).

각 값이 마지막으로 나온 위치를 해시 맵에 기억해 두면, nums[r]이 이미 구간 안(last ≥ l)에 있을 때 l = last + 1로 한 번에 옮길 수 있습니다. 그러면 전체가 O(N)O(N)입니다.

시작점마다 집합을 새로 만들어 겹칠 때까지 늘리는 풀이는 값이 대부분 서로 다를 때 O(N2)O(N^2)이 되어 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251234 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.