双指针算法练习

目录一、唯一的雪花二、逛画展三、字符串四、丢手绢一、唯一的雪花UVA11572 唯一的雪花 Unique Snowflakes - 洛谷答案如下#includeiostream #includeunordered_map using namespace std; const int N 1e6 10; int a[N]; int main() { unordered_mapint,int mp; int t; cin t; while(t--) { int n; cin n; for(int i 0; i n; i) { cin a[i]; } int ret 0; for(int left 0, right 0; right n; right) { mp[a[right]]; while(mp[a[right]] 1) { mp[a[left]]--; left; } ret max(ret,right - left 1); } cout ret endl; } return 0; }二、逛画展P1638 逛画展 - 洛谷答案如下#includeiostream #includeunordered_map using namespace std; const int N 1e6 10; int a[N]; int main() { int n,m; cin n m; for(int i 1; i n; i) { cin a[i]; } int count 0; int minPrice N; int begin 0, end 0; unordered_mapint,int hash; for(int left 1, right 1; right n; right) { int in a[right]; if(hash[in] 0) { count; } hash[in]; while(count m) { if(right - left 1 minPrice) { minPrice right - left 1; begin left; end right; } int out a[left]; if(hash[out] 1) { count--; } hash[out]--; left; } } cout begin end endl; return 0; }三、字符串字符串答案如下#includeiostream #includestring using namespace std; int Hash[26]; int main() { string s; cin s; int count 0; int lenth 1e6 10; for(int left 0, right 0; right s.size(); right) { int in s[right]-a; if(Hash[in] 0) { count; } Hash[in]; while(count 26) { lenth min(lenth,right-left1); int out s[left]-a; if(Hash[out] 1) { count--; } Hash[out]--; left; } } cout lenth endl; return 0; }四、丢手绢丢手绢答案如下#includeiostream using namespace std; const int T 1e510; int a[T]; int main() { int N; cin N; int sum 0; for(int i 1; i N; i) { cin a[i]; sum a[i]; } int ret 0, Lmax -1; for(int left 1, right 1; right N; right) { ret a[right]; while(ret sum/2) { ret - a[left]; left; } Lmax max(ret,Lmax); } cout Lmax endl; return 0; }