[C++知识库]C++滑动窗口

1、题意

给定一个字符串s，找出其中不含有重复字符的最长子串的长度。

2、思路

1）贪心
从字符串中任意一个位置开始，向两端扩展，直到出现重复的，记录不重复的子串长度。以此方式从s的每个字符开始。

2）滑动窗口
使用两个指针L,R,R在右边，L在左边，【L,R】表示整个滑动窗口；从s第一个字符开始遍历，若未出现重复的字符，R向右移动，若出现重复的字符串，向右移动L直到【L，R】窗口中不再有重复的字符，将当前的窗口大小和保存的最大子串长度比较，取较大者。

本文源码实现的是滑动窗口。

3、源码

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
    	int length = s.length();
    	int l = 0,r = 0;
    	int ret = 0;
    	map<char,int> count;//记录窗口中每个字符的出现次数
    	for(;r < length; r++)
    	{
    		count[s[r]]++;
    		while(count[s[r]] >= 2)
    		{
    			count[s[l++]]--;//先count--在l++
    		}
    		ret = max(ret, r - l + 1);
    	}
    	return ret;
    }
}

以上内容如有不足之处请不吝指出。