题目:给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串的长度。
C++:
指针法,使用at读取字符串中的值;
#include <iostream>
#include <string>
#include <vector>
#include <windows.h>
using namespace std;
// 指针法,使用at读取数组中的值
class Solusion
{
public:
int lengthOfLongestSubstring(string s)
{
int maxLength = 0, start = 0, end = 0, j = 0;
for (int i = 0; i < s.size(); ++i) // ++i:说明先执行在赋值,i++:先赋值在执行
{
end = i;
for (j = start; j < i; ++j)
{
if (s.at(i) == s.at(j))
{
start = j + 1;
maxLength = (maxLength > end - start + 1) ? maxLength : (end - start + 1);
break;
}
}
maxLength = (maxLength > end - start + 1) ? maxLength : (end - start + 1);
}
return maxLength;
}
int main(int argv, void **argc)
{
Solusion s;
//string a = "abcabcbb";
cout << "length==" << s.lengthOfLongestSubstring("abcabcbb") << endl;
system("pause");
return 1;
}
python:
滑动窗口法思路:
首先,我们定义窗口的两端:begin和end,分别表示要找的子串的开头和结尾。
开始的时候,begin和end都指向0的位置即‘a’,然后end不断后移(窗口变宽),当遇到第二个‘a’时(遇见重复字符)就得到一个子串,其长度就是end和begin位置的差。
定义一个字典,用于存放end从头开始遇到的每个字符及其索引位置,end每次移动到新字符就查一下字典即可。
通过字典,我们遇到第二个‘a’时就可以找到存在字典里面的第一个‘a’的位置。为了继续寻找无重复子串,begin就要指向第一个‘a’后面一个的位置即‘b’。然后end继续后移到‘b’,有发现它与前面的‘b’重复,计算子串长度赋值给最大长度(需要比较),同时begin要移动第一个‘b’后面的位置即‘c’。
这样依次移动end到字符串末尾就可以找到最长的子串,“子串窗口”也就从头移到了末尾。而只需要end从头到尾的一次循环即可。
class Solution(object):
def lengthOfLongestSubstring(self, s):
maxlen = 0
tmp_dict = dict()
begin, end = 0, 0
n = len(s)
while end < n:
last = tmp_dict.get(s[end])
tmp_dict[s[end]] = end
if last is not None:
maxlen = max(maxlen, end-begin)
begin = max(begin, last + 1)
end += 1
maxlen = max(maxlen, end-begin)
return maxlen
if __name__ == '__main__':
sol = Solution()
print(sol.lengthOfLongestSubstring("bbbbb"))