题目:
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
给定 "abcabcbb"
,没有重复字符的最长子串是 "abc"
,那么长度就是3。
给定 "bbbbb"
,最长的子串就是 "b"
,长度是1。
给定 "pwwkew"
,最长子串是 "wke"
,长度是3。请注意答案必须是一个子串,"pwke"
是 子序列 而不是子串。
暴力解决方法:
首先枚举出所有的子串,用star记录子串的起始点,end记录子串的末尾。枚举出所有的子串之后,开始检查子串中是否存在重复的字符,若存在则该子串不符合要求,若该子串中不存在重复的字符,那么将该子串的长度与之前的最大长度相比,若比最大长度还长,那么更新最大长度的值。最后返回最长长度。
要点:
(1)枚举出所有的子串 (2)要求该子串中没有重复的字符,若存在重复的字符则不符合题目要求(3)更新不重复子串中的长度
代码实现(c语言)
/*更新最长长度*/
int Max(int a, int b)
{
int max=0;
return max = a>b?a:b;
}
/*检查字符ch是否存在在数组st中*/
int contain(char *st, char ch)
{
int len = strlen(st);
for(int i=0; i<len; i++)
{
if(st[i]==ch)
{
return 1;
}
}
return 0;
}
int judge(char *s, int star, int end)
{
int len = strlen(s);
int k = 0;
char *st;
st = (char *)malloc(end+1-star);
/*判断子串是否重复,需要一个数组st来保存之前的字符,然后用当前字符与之前字符做比较,若不重复,将当前字符加入st数组中为下次比较做准备*/
for(int i=star; i<end; i++)
{
if(!contain(st,s[i]))
{
st[k++] = s[i];
}
else{
return 0;
}
}
return 1;
}
int lengthOfLongestSubstring(char* s) {
int len = strlen(s);
int max = 0;
/*枚举出所有的子串*/
for(int i=0; i<len; i++)
{
for(int j=i+1; j<=len; j++)
{
if(judge(s,i,j))//若该子串不重复
{
max = Max(max, j-i);//j-i为当前子串的长度,更新最长长度
}
}
}
return max;
}
c++实现:
class Solution {
public:
int Max(int a, int b)
{
int max = a;
return max = a>b?a:b;
}
bool judge(string s, int star, int end)
{
string st="";
for(int i=star; i<end; i++)
{
if(st.find(s[i])==st.npos)//该元素在子串中不重复
{
st.insert(st.end(),s[i]);
}
else{
return false;
}
}
return true;
}
int lengthOfLongestSubstring(string s) {
int max = 0,i=0,j=0;
int len = s.size();
for(int i=0; i<len; i++)
{
for(int j=i+1; j<=len; j++)
{
if(judge(s,i,j))
{
max = Max(max, j-i);
}
}
}
return max;
}
};
滑动窗口解决方法:
暴力解决方法,通常要反复的查看子串中是否有重复的字符。那么假设从i到j-1之间的子串中没有重复的字符了,那么只需要坚持S[j]的元素是否与i到(j-1)中的重复。要检查一个字符是否已经在子字符串中,我们可以检查整个子字符串,这将产生一个复杂度为 O(n^2) 但是利用滑动窗口的话,可以用时间复杂度为O(1)来完成子串中的检查。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i,j)[i,j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i,j)[i,j)向右滑动 11 个元素,则它将变为 [i+1,j+1)[i+1,j+1)(左闭,右开)。所以在该问题中,同时设置索引i,j 最开始两个索引的位置是相同的,都在下标为0处。然后j开始往右滑动,滑动前要检查,j此时所在的位置的元素是否和之前的字符重复,若不重复的话,将s[j]加入到st中,并且更新最长子串长度。若此时j所在的位置的元素和之前子串中的重复,此时j不再滑动,此时删除st中的s[i],并且滑动i,使得st的范围一直在i和j之间。
代码实现(C++)
class Solution {
public:
int Max(int a, int b)
{
int max = a;
if(b > max)
{
return b;
}
else
{
return a;
}
}
int lengthOfLongestSubstring(string s) {
int max = 0,i=0,j=0;
int len = s.size();
string st="";
while(i<len && j<len)
{
//j在子串中不重复
if(st.find(s[j])==st.npos)
{
st.insert(st.end(),s[j]);
j++;
max = Max(max, j-i);
}
else
{
st.erase(st.find(s[i]),1);
i++;
}
}
return max;
}
};