Peter算法小课堂—蠕动区间

蠕动区间

蠕动区间（尺取法、双游标）是一个经典的优化算法。

我们以毛毛虫🐛举例说明

具体的，我们看题目

例题

最小区间

 这一题，我们用暴力法，复杂度O(N^2)

先给出暴力法代码

int ans=n+1;
for(int tail=0;tail
	int sum=0;
	for(int head=tail;head
		sum+=x[head];
		if(sum>=m){
			ans=min(ans,head+1-tail);
			break;
		}
	}
}
cout<

 我们看一下蠕动区间怎么写

上面有注释，大家看不明白就私信哦

收集三原色

这道题更难一点……

数据结构

string x[N];
mapint> cnt;
set rgb;
rgb.insert("red");
rgb.insert("green");
rgb.insert("blue");

主体部分

int sum=0,ans=n+1;
int tail=0,head=0;
while(1){
	while(head3){
		string color=x[head++];
		if(!rgb.count(color)) continue;
		++cnt[color];
		if(cnt[color]==1) sum++;
	}
	if(sum<3) break;
	ans=min(ans,head-tail);
	string color=x[tail++];
	if(!rgb.count(color)) continue;
	--cnt[color];
	if(cnt[color]==0) sum--;
}
cout<

希望这些对大家有用，三联，必回