사용한 것
- 연속한 수열 중에서 같은 수가 중복되지 않는 수열의 개수를 구하기 위한 투포인터
풀이 방법
- 기준 인덱스
l
에서 r
을 증가시키면서 같은 수가 중복되지 않는 수열의 개수를 구한다.
- 구간
l
~ r
에서 연속한 수가 없었다면, 개수는 r
- l
- 1 이다.
- 연속한 수가 등장하거나 배열의 크기를 초과했다면
l
을 1 증가시킨다.
r
까지의 인덱스는 중복되지 않음이 보장되기에 그대로 사용한다.
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int l = 1;
int r = 0;
long answer = 0;
int[] ct = new int[100_001];
while (l <= n) {
while (r + 1 <= n && ct[arr[r + 1]] == 0) {
r++;
ct[arr[r]]++;
}
answer += r - l + 1;
ct[arr[l++]]--;
}
System.out.println(answer);
}
}