LeetCode上的第三题。

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

这道题并不算很难,因为算法的逻辑跟手动查找一样。给一个字符串,s= “abcabcbb”,我们的直觉是从左往右,一个字符一个字符得查看,并且维护一个连续的子串L,在查看的同时,更新这个子串,这个子串也在最后被返回。这个子串是原来字符串的一个区间(又称滑动窗口),假设记录为W = [i,j)。
其中,i为子串最左边界,我们可以用一个全局变量left来记录当前子串的左边界。

查看下一个字符s[j]时,要跟维护的子串L进行比较,判断是否s[j]已经在L中。但是,遍历子串L一个一个查找,当然是不恰当的。由于每个字符在子串中最多出现一次,因此字符如果在当前的滑动窗口内,就记录下字符的位置。

这里我们可以建立一个256位大小的整型数组来代替HashMap,这样做的原因是ASCII表共能表示256个字符,所以可以记录所有字符,然后我们需要定义两个变量res和left,其中res用来记录最长无重复子串的长度,left指向该无重复子串左边的起始位置,然后我们遍历整个字符串,对于每一个遍历到的字符,如果哈希表中该字符串对应的值为0,说明没有遇到过该字符,则此时计算最长无重复子串,i - left +1,其中i是最长无重复子串最右边的位置,left是最左边的位置,还有一种情况也需要计算最长无重复子串,就是当哈希表中的值小于left,这是由于此时出现过重复的字符,left的位置更新了,如果又遇到了新的字符,就要重新计算最长无重复子串。最后每次都要在哈希表中将当前字符对应的值赋值为i+1。

  1. L=[],left = 0 (left 窗口左边界,为字符下标)
  2. 查看第1个字符,“a”, 此时m[a] = 0;
  3. L中加入“a”,L= “a”, W=[1,2), left = 0,m[a]=1
  4. 查看第2个字符,“b”,m[b] = 0;
  5. L中加入"b",L= “ab”, W= [1, 3),left = 0,m[b] = 2;
  6. 查看第3个字符,“c”,m[c] = 0;
  7. L中加入"c",L= “abc”, W = [1, 4],left = 0,m[c] = 3;
  8. 查看第4个字符,“a”,m[a] = 1,(m[a] > left) 说明a在当前窗口内;
  9. L中加入"a",L= “bca”, W = [2, 5),left = m[a] , (left右滑,直接到L中a的下一位), 当前a的下标4;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = {0};
int max_len = 0;
int left = 0;
for(int right = 0; right < s.size(); right ++){
if ( m[s[right]] == 0 || m[s[right] < left]) // 当前字母没出现过,或者在窗口左侧
max_len = max(max_len, right - left +1);
else
left = m[s[i]]; // left 右滑
}
return max_len;
};