Tips:所有代码实现包含三种语言（java、c++、python3）
题目
Given a string, find the length of the longest substring without repeating characters.
给定字符串，找到最大无重复子字符串。
样例
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Input: "pwwkew"
Output: 3
Explanation: 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.
解题
首先看到：
输入：一个字符串
输出：最大无重复子字符串的长度
优秀的程序猿很快理解了问题，并且快速给出了第一个思路：
计算以字符串中的每个字符作为开头的子字符串的最大长度，然后选取最大长度返回；
那么问题就变了简单了：求解字符串中以某个字符开头的最大无重复子字符串 ，这里我们借助 Set 实现判断子字符串中是否无重复。
具体步骤如下：
- 遍历字符串中每个字符，并执行步骤2；
- 构建一个 Set，用于记录子字符串所包含字符，逐个添加此字符之后的字符进入 Set，直至 Set 中已包含此字符；
- 比较所有无重复子字符串的长度，返回最大值；
//java
// Runtime: 77 ms, faster than 17.83% of Java online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 39.4 MB, less than 19.93% of Java online submissions for Longest Substring Without Repeating Characters.
public int lengthOfLongestSubstring(String s) {
if(s.length()==0) return 0;
if(s.length()==1) return 1;
char[] schars = s.toCharArray();
int max = 0;
for(int i = 0; i < schars.length; i++){
HashSet<Character> curSet = new HashSet<Character>();
int j = i;
for(; j < schars.length; j++){
if(curSet.contains(schars[j])){
break;
}
curSet.add(schars[j]);
}
max = Math.max(max, j-i);
}
return max;
}
// c++
// Runtime: 900 ms, faster than 6.82% of C++ online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 271 MB, less than 5.03% of C++ online submissions for Longest Substring Without Repeating Characters.
int lengthOfLongestSubstring(string s) {
if(s.length()==0) return 0;
if(s.length()==1) return 1;
int result = 0;
for(int i = 0; i < s.length() - result; i++){
unordered_set<char> curSet;
int j = i;
for(; j < s.length(); j++){
if(curSet.find(s[j]) != curSet.end()){
break;
}
curSet.insert(s[j]);
}
result = max(result, j-i);
}
return result;
}
# python3
# Runtime: 2456 ms, faster than 5.01% of Python3 online submissions for Longest Substring Without Repeating Characters.
# Memory Usage: 13.4 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0: return 0
if len(s) == 1: return 1
result = 0
i = 0
while i < len(s) - result:
j = i
cur_list = []
while j < len(s):
if s[j] in cur_list:
break
cur_list.append(s[j])
j+=1
result = max(result, len(cur_list))
i+=1
return result
可以看到，虽然算法是正确的，但是 runtime 表现很差，优秀的程序猿不满足于此；
再审视一遍题目：
给定字符串，找到最大无重复子字符串
优秀的程序猿敏锐的捕捉到了两个关键词 "找到"、"子字符串" ，脑子里猛地蹦出来一个思路：滑动窗口（Sliding Window） ；
滑动窗口（Sliding Window） ：设立两个游标，分别指向字符串中的字符，两个游标作为窗口的左右边界用来表示窗口，也就是子字符串；
对于滑动窗口（Sliding Window），我们必须明确以下几点：
- 窗口代表什么？
- 左右边界代表什么？
- 左右边界的滑动时机？
首先我们知道，在本题中，窗口代表的就是无重复子字符串，左右边界分别代表子字符串的两端；
对于滑动时机，在本题中，我们限定右边界的滑动为主滑动，也就是说，右边界的滑动为从字符串最左端至最右端；而对于左边界，其滑动跟随右边界的滑动，每当右边界发生滑动，那么判断新纳入字符是已存在当前窗口中，如不存在，左边界不动，如存在，则将左边界滑动至窗口中此已存在字符之后，可看出此操作保证了窗口中一定不存在重复字符；
每当窗口发生变化，更新最大窗口长度，当右边界滑动至字符串最右端时结束并返回最大长度；
随着右边界的滑动，我们使用 map 记录每个字符最后出现的位置，以便于左边界的滑动更新；
// java
// Runtime: 17 ms, faster than 96.07% of Java online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 39.1 MB, less than 23.13% of Java online submissions for Longest Substring Without Repeating Characters.
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length()==0) return 0;
if(s.length()==1) return 1;
char[] schars = s.toCharArray();
Map<Character, Integer> sMap = new HashMap<>();
int max = 0;
int start=0, end=0;
for(; end < schars.length; end++){
if(sMap.containsKey(schars[end])){
start = Math.max(start, sMap.get(schars[end]));
}
sMap.put(schars[end], end+1);
max = Math.max(max, end-start+1);
}
return max;
}
// c++
// Runtime: 28 ms, faster than 67.81% of C++ online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 16.3 MB, less than 52.86% of C++ online submissions for Longest Substring Without Repeating Characters.
int lengthOfLongestSubstring(string s) {
if(s.length()==0) return 0;
if(s.length()==1) return 1;
int result = 0;
unordered_map<char, int> sMap;
int start=0, end=0;
for(; end < s.length(); end++){
if(sMap.count(s[end])){
start = max(start, sMap[s[end]]);
}
sMap[s[end]] = end+1;
result = max(result, end-start+1);
}
return result;
}
# python3
# Runtime: 92 ms, faster than 63.67% of Python3 online submissions for Longest Substring Without Repeating Characters.
# Memory Usage: 13.5 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0: return 0
if len(s) == 1: return 1
result = 0
s_dict = {}
start = 0
for idx, ch in enumerate(s):
if ch in s_dict:
start = max(start, s_dict[ch])
s_dict[ch] = idx+1
result = max(result, idx-start+1)
return result
runtime 表现不错，不过优秀的程序猿觉得任有瑕疵，既然我们处理的数据被限定为字符串，那我们其实没必要使用 map ，使用长度为 256 的数组就完全可以起到 map 的作用；
优秀的程序猿又欢快的修改了答案
// java
// Runtime: 15 ms, faster than 99.32% of Java online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 40 MB, less than 13.57% of Java online submissions for Longest Substring Without Repeating Characters.
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length()==0) return 0;
if(s.length()==1) return 1;
char[] schars = s.toCharArray();
int[] lastIndex = new int[256];
int max = 0;
int start = 0, end = 0;
for(; end < schars.length; end++){
start = Math.max(start, lastIndex[(int)schars[end]]);
lastIndex[(int)schars[end]] = end+1;
max = Math.max(max, end-start+1);
}
return max;
}
// c++
// Runtime: 16 ms, faster than 99.18% of C++ online submissions for Longest Substring Without Repeating Characters.
// Memory Usage: 14.6 MB, less than 97.14% of C++ online submissions for Longest Substring Without Repeating Characters.
int lengthOfLongestSubstring(string s) {
if(s.length()==0) return 0;
if(s.length()==1) return 1;
int result = 0;
int lastIndex[256];
memset(lastIndex, 0x00000000, sizeof(int)*256);
int start=0, end=0;
for(; end < s.length(); end++){
start = max(start, lastIndex[s[end]]);
lastIndex[s[end]] = end+1;
result = max(result, end-start+1);
}
return result;
}
# python3
# Runtime: 92 ms, faster than 63.67% of Python3 online submissions for Longest Substring Without Repeating Characters.
# Memory Usage: 13.5 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0: return 0
if len(s) == 1: return 1
result = 0
lastIndex = [0 for i in range(256)]
start = 0
for idx, ch in enumerate(s):
start = max(lastIndex[ord(ch)], start)
lastIndex[ord(ch)] = idx+1
result = max(result, idx-start+1)
return result
优秀的程序猿又严谨得审视了几遍代码，满意得合上了电脑。。。
网友评论