首页 > 代码库 > LeetCode 记录之求最长子串

LeetCode 记录之求最长子串

//the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
//每个数组里保留的值都是字符最新的位置,用一个数值保存字符的位置,一个数值保存最长子串的长度,如果当前字符串位置比之前字符串位置大,则保留当前位置,否则记录之前的位置,递归求出最大子串的长度
int longestsubstring(string s)
{
	vector<int>CharRecoder(256,-1);
	int maxLength,c=0;
	for (int i=0;i<s.size();i++)
	{
		c=max(CharRecoder[s[i]]+1,c);
		CharRecoder[s[i]]=i;
		maxLength=max(maxLength,i-c+1);
	}
	return maxLength;
}

  

LeetCode 记录之求最长子串