这是一个双指针问题,还要用到STL;
题目要求找出没有相同个数(每个数只出现一次)的最长区间
这题的最优解是应用哈希,但是我不会哈希所以用map来写
先定义一个左指针left,在用一个右指针right进行移动,如果右指针指向从未出现过的数那么将此数放入map,之后标记这个数已经出现,right++,走到下一个数,如果这个数出现过,那么左指针右移,直到找到第一次出现的这个数,进行删除;遍历一遍可知符合条件的最长区间max_len并记录下来,第二次遍历找的等于最大长度的所有区间的个数和所有区间(也可能只有一个)将它输出
注:我的代码是从0位置开始遍历,所以答案区间要加1(最好从1开始遍历)。
下列是该问题的一种解法:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>arr(n,0);//存储原始数组
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
map<int,int>brr;//存储出现过的数
vector<pair<int,int>>crr;//存储符合题目的所有区间的答案
int left=0;//左指针
int max_len=0;//最大长度
//第一次循环为了寻找最大长度;
for(int right=0;right<n;right++)
{
while(brr[arr[right]])
{
brr[arr[left]]--;
left++;
}
brr[arr[right]]++;
int len=right-left+1;
if(len>=max_len)
{
max_len=len;
}
}
left=0;
brr.clear();
//第二次循环为了查找最大长度的多个区间
for(int right=0;right<n;right++)
{
while(brr[arr[right]]>0)
{
brr[arr[left]]--;
left++;
}
brr[arr[right]]++;
int len=right-left+1;
if(len==max_len)
{
crr.push_back({left+1,right+1});//(从0位置遍历left+1,right+1)
}
}
cout<<crr.size()<<endl;
for(auto x:crr)
{
cout<<x.first<<" "<<x.second<<endl;
}
return 0;
}



京公网安备 11010502036488号