[leetcode][992] Subarrays with K Different Integers

문제 : https://leetcode.com/problems/subarrays-with-k-different-integers/

---

투포인터로 풀었다.

A = 2212211이고 K가 2일 때를 예로 들어보자.

인덱스 r이 1일 때,

인덱스 l은 K가 2일때를 만족하는 인덱스 0부터 시작한다.

이 때, 인덱스 r을 포함시키는 정답이 될 수 있는 경우의 수를 구한다.

인덱스 0부터 A[i]의 개수가 1개일 때까지 l을 증가시킨다.

정답이 될 수 있는 경우는 이 때 인덱스 l의 증가량 +1이 된다.

정답이 될 수 있으려면 최소한 1개의 범위 내에 각 숫자를 최소한 한 개는 가지고 있어야 한다.

즉, 인덱스 r을 포함한 정답가능한 최소 문자열은 위 그림과 같이 "2 1" 이다.

여기에서 K가 2일 때를 만족하는 범위의 인덱스들을 하나씩 앞에 추가해가면 이는 모두 정답이 될 수 있기 때문에 정답 가능한 최소 범위를 구하기 위해 A[i]의 개수가 1개일 때까지 l을 증가시킨 것이다.

만약 A = [1, 2, 1, 3] 이고 K=2 일 때, r인덱스가 2에서 3으로 증가한다고 하자.

이 때 l인덱스는 0에서 2로 변경되어야 한다.

l인덱스의 변경점은 어떠한 값의 개수가 0개를 만들 때까지 l을 증가시키면 된다.

위 예제에서는 2의 개수가 0이 될때까지 l을 증가시켰다.

l을 2에서부터 앞에서 한 것처럼 정답 가능한 경우의 수를 찾으면 된다.

시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/1174d3748a24722928c6210b8fecd30f