백준 13144. List of Unique Numbers (투포인터)

https://www.acmicpc.net/problem/13144

13144번: List of Unique Numbers

연속하는 부분 수열의 개수를 묻는 문제이므로 투포인터를 사용하면 된다. 

 

1. 특징 

1) 투포인터

2) 연속한 값이 부분 수열에 있는 지 확인하기 위해 bool형 배열 사용

 

2. 코드

#include <iostream>
using namespace std;

// 투포인터
int n;
int a[100002];
bool v[100002];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }    

    int en = 0;
    v[a[0]] = true;
    long long ans = 0;

    for(int st = 0; st < n; st++)
    {
        while(en < n - 1)
        {
            en++; 
            if(v[a[en]] == false)
            {
                v[a[en]] = true;
            }
            else
            {
                en--;
                break;
            }
        }
        ans += (en-st+1);
        v[a[st]] = false;

    }

    cout << ans;

}