Count subarrays having exactly K elements occuring at least twice

#include <bits/stdc++.h>

using namespace std;

  

int cntSubarrays(int A[], int K, int n)

{

    

    

    

    int cntSub = 0;

  

    

    

    map<int, int> mp;

  

    

    

    int l = 0, r = 0;

  

    

    

    set<int> st;

  

    

    while (r < n) {

  

        

        

        while (r < n && st.size() <= K) {

  

            

            if (mp[A[r]]) {

                st.insert(A[r]);

            }

  

            

            mp[A[r]]++;

  

            

            r++;

  

            

            if (st.size() == K)

                cntSub++;

        }

  

        

        

        while (l < r && st.size() > K) {

  

            

            cntSub++;

  

            

            mp[A[l]]--;

  

            

            if (mp[A[l]] == 1) {

                st.erase(st.find(A[l]));

            }

  

            

            l++;

        }

    }

  

    

    

    while (l < n && st.size() == K) {

  

        

        cntSub++;

  

        mp[A[l]]--;

  

        

        if (mp[A[l]] == 1) {

            st.erase(st.find(A[l]));

        }

  

        

        l++;

    }

  

    

    return cntSub;

}

  

int main()

{

    int arr[] = { 1, 1, 1, 2, 2 };

    int K = 1;

    int N = sizeof(arr) / sizeof(arr[0]);

  

    cout << cntSubarrays(arr, K, N);

  

    return 0;

}

Let's block ads! (Why?)