[LeetCode] 3. Longest Substring Without Repeating Characters(无重复字符的最长子串)-滑动窗口法
本题是 amazon、Adobe、yelp、Bloomberg的面试题。
问题描述:
方法一:滑动窗口法
解题思路:
①设定两个滑动指针 i 和 j,区间 s[ i ... j ]为滑动窗口:
②滑动指针j,
③知道遇到了重复的字符:
此时记录没有重复字符串的长度。
④然后将左指针 i 向右滑动,知道没有重复字符
Note:我们定义一个数组freq[256]来记录重复字符,如果freq[256] = 1,表示有一个重复字符, freq[256] = 0,表示没有重复字符。
实现代码:
// 时间复杂度: O(len(s))
// 空间复杂度: O(len(charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = { 0 };
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 整个循环从 l == 0; r == -1 这个空窗口开始
// 到l == s.size(); r == s.size()-1 这个空窗口截止
// 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
while (l < s.size()) {
if (r + 1 < s.size() && freq[s[r + 1]] == 0) {
++r;
freq[s[r]] ++; //元素 s[r] 出现的频率 + 1
}
else //r已经到头 || freq[s[r+1]] == 1
{
freq[s[l]] --; //元素 s[l] 出现的频率 - 1
l++;
}
res = max(res, r - l + 1);
}
return res;
}
};
int main() {
cout << Solution().lengthOfLongestSubstring("abcabcbb") << endl; //3
cout << Solution().lengthOfLongestSubstring("bbbbb") << endl; //1
cout << Solution().lengthOfLongestSubstring("pwwkew") << endl; //3
cout << Solution().lengthOfLongestSubstring("c") << endl; //1
cout << Solution().lengthOfLongestSubstring("") << endl; //0
getchar();
return 0;
}
方法二、改进的滑动窗口法
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
Explanation:
在初始状态,定义一个向量 vector<int> dict(256, -1); vector的大小为256,每个数定义初始化为-1;
①当 i = 0时 ,
②当 i = 1 时;
③当 i = 2时;
③ 当 i = 3 时;
此时,dict[ a ] > start;
然后将start 指针移动到重复元素 a 的位置:(涂色部分为窗口)
④当 i = 4 ,
⑤ 当 i = 5 时,
⑥当 i = 6 时,
⑦当 i = 7时,
整个数组遍历完成。
Reference: