滑动窗口(c++双指针算法，四题)

滑动窗口本质上是对于暴力算法的优化，采用的是双指针算法中的左右指针，对于暴力算法的优化。
滑动窗口的基本模板
while(right 
  
 
 思考四个问题 
 1.移动right扩大窗口，即加入字符时，需要更新哪些数据 
 2.什么条件下，窗口应该暂停扩大，开始移动left缩小窗口 
 3.当移动left缩小窗口，即移出字符时，应该更新哪些数据 
 4.我们要的结果是在扩大窗口时还是在缩小窗口时更新 
 
四个问题在滑动窗口的问题中都会出现，但是每个不同的题目，这四个问题的答案都是不同的，应该具体问题具体分析 
 
1.最小覆盖子串 
 
题目的要求：窗口中包含子串所有的字符，且数量一致  
四个答案： 
1.移动right扩大窗口，即加入字符时，需要更新哪些数据 
移动right时，需要更新窗口中的数据(windows),当前已满足元素(valid) 
2.什么条件下，窗口应该暂停扩大，开始移动left缩小窗口 
窗口已经满足题目要求了，即valid==needs.size(),窗口已包含子串元素个数==子串元素总个数 
3.当移动left缩小窗口，即移出字符时，应该更新哪些数据 
移出字符时，应该判断窗口元素是否减小，减小了的话valid是否减小 
4.我们要的结果是在扩大窗口时还是在缩小窗口时更新 
缩小窗口，因为扩大窗口是让我们满足完全包含子串中的元素，缩小窗口是为了让我们找到满足要求的最小窗口 
#include 
#include 
#include 

using namespace std;


string minwindows(string t, string s)
{
	const int MAXINT = 0x3f3f3f;
	map windows, needs;
	//windows包含放入窗口的在needs内的字母	needs包含t的字母
	int start = 0, len = MAXINT;
	int left = 0, right = 0;
	int valid = 0;	//已满足的字符种类
	for (char c : t)
		needs[c]++;
	while (right < s.size())
	{
		char c = s[right];
		right++;	//右移窗口
		
	//更新,向右扩展到满足要求:正好包含字符种类
		if (needs.count(c))
		{//c是被需要的
			windows[c]++;		
			if (windows[c] == needs[c])
				valid++;		//只有一种字母数量满足要求，valid++
		}
	//满足要求后，开始缩小窗口
		while (valid == needs.size())
		{
	//更新答案
			if (right - left < len)
			{
				start = left;
				len = right - left;
			}
			char d = s[left];
			left++;		//左移窗口，找到最小
	//缩小的时候要更新窗口中的值		
			if (needs.count(d))
			{//d在needs中，左移窗口被舍弃，需要更新
				if (windows[d] == needs[d])	//被舍弃后不满足要求，valid需要-1
					valid--;
				windows[d]--;
			}
		}
	}
	return len == MAXINT ? "" : s.substr(start, len);
}

int main()
{
	string s = "ADOBECODEBANC", t = "ABC";
	cout << minwindows(t, s);
}
 
2.字符串的排列 
 
 题目要求：窗口中仅包含子串中的元素且数量相同 
#include 
#include 
#include 
using namespace std;

bool checkInclusion(string s1, string s2)
{
	map windows, needs;
	for (char c : s1)
		needs[c]++;
	int valid = 0;
	int left = 0, right = 0;
	while (right < s2.size())
	{
		char c = s2[right];
		right++;
		if (needs.count(c))
		{
			windows[c]++;
			if (windows[c] == needs[c])
				valid++;
		}
		while (valid == needs.size())		//全部满足了
		{
			if (right - left == s1.size())
				return true;
			char d = s2[left];
			left++;
			if (needs.count(d))
			{
				if (windows[d] == needs[d])
					valid--;
				windows[d]--;
			}
		}
	}
	return false;
}
int main()
{
	string s1, s2;
	s1 = "ab";
	s2 = "eidboaoo";
	cout << checkInclusion(s1, s2);
	return 0;
} 
3.找字符串中所有字母的异位词 
 
  题目要求：窗口中仅包含子串中的元素且数量相同 
#include 
#include 
#include 
#include 
#include 
using namespace std;

vector findAnagrams(string s, string p) 
{
	vector  ans;
	int right = 0;
	int left = 0;
	map  windows, needs;
	for (char c : p)
		needs[c]++;
	int valid = 0;
	while (right < s.size())
	{
		char c = s[right];
		right++;
		if (needs.count(c))
		{
			windows[c]++;
			if (windows[c] == needs[c])
				valid++;
		}
		while (valid == needs.size())
		{
			if (right - left == p.size())
			{
				ans.push_back(left);
			}
			char d = s[left];
			left++;
			if (needs.count(d))
			{
				if (windows[d] == needs[d])
					valid--;
				windows[d]--;
			}
		}
	}
	return ans;
}
int main()
{
	string s = "abab", p = "ab";
	for(int a:findAnagrams(s,p))
		cout< 
4.不含重复字母的最小子串 
 
 题目要求：窗口中不能有重复的字符，且窗口的长度要最大 
#include 
#include 
#include 
using namespace std;

int lengthOfLongestSubstring(string s)
{//给定一个字符串，找出字符串中不包含重复字符的最长子串
	map windows;
	int left = 0, right = 0;
	int maxL = -1;
	while (right < s.size())
	{	
		char c = s[right];
		right++;
		windows[c]++;
		while (windows[c] > 1)
		{
			char d = s[left];
			left++;
			windows[d]--;
		}
		maxL = max(maxL, right - left);
	}
	return maxL;
}
int main()
{
	string s= "aabccccc";
	cout<
滑动窗口(c++双指针算法，四题)

C/C++/C#相关栏目本月热门文章
