프로그래밍

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

[난이도] Gold3
[유형] 투 포인터

[풀이]
a[i],a[i+1],a[i+2],..,a[j] 까지 같은 수가 여러번 나타나지 않을 때, a[i]를 반드시 선택하면 총 j-i+1개의 경우의 수가 있습니다.
만약 a[i+1]를 반드시 선택하면 a[i+1]~a[j] 까지 j-1개의 경우의 수가 확보가 되고, a[i]를 선택하지 않았기 때문에
a[j+1]부터 수열에 이미 포함된 나올때까지 j의 범위를 넓혀갈 수 있습니다.
위의 성질을 이용해 set에 수열에 포함된 숫자들을 저장해가며 i를 left, j를 right로 하는 투포인터를 구현해주면 됩니다.

#include <cstdio>
#include <set>
using namespace std;
using ll = long long;
int N,a[100001];
ll ans;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    int j=1;
    set<int> st={a[1]};
    for(int i=1;i<=N;i++){
        ans+=st.size();
        for(int k=j+1;k<=N+1;k++){
            if(k==N+1) {
                j=N+1;
                break;
            }
            if(st.find(a[k])!=st.end()) {
                j=k-1;
                break;
            }
            st.insert(a[k]);
            ans++;
        }
        st.erase(a[i]);
    }
    printf("%lld",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/13144.cpp