leetcode 3. 无重复字符的最长子串----滑动窗口篇1，双指针篇1

class Solution {
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;
		int start(0), end(0), maxLength(1),len(0);
		for (; end < s.size(); end++)
		{
			char temp = s[end];
			for (int j = start; j < end; j++)
			{
				if (s[j] == temp)//当前滑动窗口出现重复字符
				{
					start = j + 1;
					//计算start指针更新后，当前滑动窗口内元素的个数，注意此时end指针指向的元素已经和滑动窗口里面任何一个元素都不重合
					//一会还需要把end指针指向的元素放入更新后的滑动窗口内，就len的长度一会还需要加一
					len = end - start;
					break;
				}
			}
			//如果当前end指针指向的元素与滑动窗口内的某个元素重复，那么start指针需要更新到新的位置，当start指针更新到新的位置后
			//我们还需要把原先没有纳入滑动窗口范围，即end指针指向的元素纳入滑动窗口范围，即len的长度要加一
			len++;
			maxLength = max(maxLength, len);
			//然后end指针再继续后移
		}
		return maxLength;
	}
};

class Solution {
	unordered_map<char, int> cache;
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;
		int start(0), end(0), maxLength(1),len(0);
		for (; end < s.size(); end++)
		{
			char temp = s[end];
			//出现重复字符----注意:仅当s[start,end) 中存在s[end]时更新start
			//因为随着滑动窗口大小和位置的变化，可能某些数据原先已经存入了哈希表中，但是随着滑动窗口大小和位置的变化
			//这些数据离开了滑动窗口的范围，但是数据依然保留在哈希表内部
			//因此这里要限制必须当前元素是与滑动窗口里面的元素重复，不包括外部
			if (cache.find(temp) != cache.end()&&cache[temp] >= start)
			{
					start = cache[temp] + 1;
					len = end - start;

		    }
			cache[temp] = end;
			len++;
			maxLength = max(maxLength, len);
		}
		return maxLength;
	}
};

class Solution {
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;
		int start(0), end(0), maxLength(1),len(0);
		vector<int> ascall(128, -1);
		for (; end < s.size(); end++)
		{
			char temp = s[end];
			//说明当前元素是和滑动窗口内元素产生重复
			if (ascall[temp] >= start)
			{
				start = ascall[temp] + 1;
				 len = end - start;
			}
			//更新当前产生重复元素的下标
			ascall[temp] = end;
			len++;
			maxLength = max(maxLength, len);
		}
		return maxLength;
	}
};

	class Solution {
public:
	int lengthOfLongestSubstring(string s) 
	{
		if (s.empty()) return 0;
		vector<int> dp(s.size());
		//当i=0时，即只有一个字符的时候，那么最长不重复子串长度就是1
		dp[0] = 1;
		for (int i = 1; i < dp.size(); i++)
		{
			//判断当前字符是否与前面dp[i-1]个字符中的字符重复
			bool found = false;
			//这里需要判断从位置i起往前dp[i-1]个字符里面是否存在两两或者多个重复元素
			//截取需要判断是否有重复元素的子串，并且进行排序，方便两两比对判断是否有重复
			string currentString = s.substr(i - dp[i-1],dp[i-1] + 1);
			sort(currentString.begin(), currentString.end());
			for (int j =0; j <dp[i - 1]; j++)
			{
				if (currentString[j] == currentString[j + 1])
				{
					found = true;
					break;
				}
			}
			//产生了重复，说明要维持当前最长不重复子串长度
			if (found)
				dp[i] = dp[i - 1];
			else
				dp[i] = dp[i - 1] + 1;
		}
		return  dp[dp.size() - 1];
	}
};