C题:求无重复数字的子串个数
本题使用双指针算法,用hash来检验是否存在相同的数
双指针l,r我们先让r一直往右走直到出现重复元素,累加起始下标为l满足条件的子串个数,再将l往左走.
样例二模拟:
8 **
**2 12 3 12 3 2 6 9
初始l=r=1,未有重复元素
直到l=1,r=4时出现重复元素我们计算下标为l开始满足条件的子串{2}{2,12}{2,12,3}ans+=r-l
下一步将l左移l=2,r=4,还有重复元素满足条件子串{12}{12,3}ans+=r-l
如此l=3,r=4时无重复r继续往前走
将上述过程用代码实现

#include<bits/stdc++.h>
using namespace std;
long long num[100005];
int main()
{
     int n;
     long long a;//方案数很多
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&num[i]);
       unordered_set<long long>mp;//哈希
       int r=1;
         a=0;
       for(int i=1;i<=n;i++)
       {   

           while(!mp.count(num[r])&&r<=n)//r往右走
           {
               mp.insert(num[r]);
               r++;
           }
           //cout<<r<<" "<<i<<endl;
               a+=r-i;
           mp.erase(num[i]);

       }
    cout<<a;
}