Simple CPP solution of O(n)


#1

int atmost(vector &A,int k) // to find atmost k distinct integers
{
int count=0,n=A.size();
int p1=0,p2=0;
unordered_map<int,int> m;
while(p2<n)
{
m[A[p2]]++;

    if(m.size()<=k)
    {count+=(p2-p1+1);}
    else
    {
        while(p1<=p2)
        {
            m[A[p1]]--;
            if(m[A[p1]]==0)
            m.erase(m.find(A[p1]));
            
            p1++;
            if(m.size()<=k)
            {
                count+=(p2-p1+1);
                break;
            }
        }
    }
    p2++;
}
return count;

}
int Solution::solve(vector &A, int B) {
return atmost(A,B)-atmost(A,B-1);
}