首页 > 代码库 > LeetCode --- 3. Longest Substring Without Repeating Characters
LeetCode --- 3. Longest Substring Without Repeating Characters
题目链接：Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
这道题的要求是在字符串中找到最长无重复字符的子串的长度。
直接思路，暴力搜索，对于每个子串都检查是否包含重复字符，时间复杂度O(n3)。
优化一下，使用l和r两个指针维护子串，用Hash表记录字串中出现的字符。每次循环r右移1位，然后判断r右移之后所指向的字符是否在Hash表中出现过：如果出现过，则表示出现重复字符，记录该子串长度，并与最长长度比较，然后逐步右移l并在Hash表中删除l指向的字符直到没有重复字符出现；如果没出现过，则说明没有重复字符，将该字符放入Hash表。
至于Hash表的建立，如果只有小写字母或是ASCII码，可以用一个数组实现。当然，也可以采用更广泛的set或是unordered_set实现。
时间复杂度：O(n)
空间复杂度：O(m)（取决于不同字符数量）
1 class Solution
2 {
3 public:
4 int lengthOfLongestSubstring(string s)
5 {
6 if(s == "")
7 return 0;
8
9 int l = 0, r = 0, maxl = 0;
10 set<char> cset;
11
12 while(r < s.size())
13 {
14 if(cset.find(s[r]) == cset.end())
15 cset.insert(s[r]);
16 else
17 {
18 maxl = max(maxl, r - l);
19 while(s[r] != s[l])
20 {
21 cset.erase(s[l]);
22 ++ l;
23 }
24 ++ l;
25 }
26 ++ r;
27 }
28 maxl = max(maxl, r - l);
29
30 return maxl;
31 }
32 };转载请说明出处：LeetCode --- 3. Longest Substring Without Repeating Characters
LeetCode --- 3. Longest Substring Without Repeating Characters