要求
- 在一个字符串中寻找没有重复字母的最长子串
举例
- 输入:abcabcbb
- 输出:abc
细节
- 字符集?字母?数字+字母?ASCII?
- 大小写是否敏感?
思路
- 滑动窗口
- 如果当前窗口没有重复字母,j右移,直到包含重复字母
- i右移,直到不包含重复字母
- 用数组记录字母是否出现过,判断重复
实现
1 class Solution{
2 public:
3 int lenthOfLongestSubstring(string s){
4 int freq[256] = {0};
5 int l = 0, r = -1;
6 int res = 0;
7
8 while(l < s.size()){
9 if( r + 1 < s.size() && freq[s[r+1]] == 0)
10 freq[s[++r]] ++ ;
11 else
12 freq[s[l++]] -- ;
13 res = max(res, r-l+1);
14 }
15 return res;
16 }
17 };
相关
- 438 Find All Anagrams in a String
- 76 Minimum Window Substring