首页 > 代码库 > 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.
这道题目不难，我自己鼓捣了一会，就写出来了。可是上网一搜，发现不是最优的。题目的tag显示要使用哈希表，我不会。
下面贴出我自己写的代码(非原稿，根据solution2作了部分修改)
solution1：
int lengthOfLongestSubstring(string s) { int len = s.size(); if(len < 2) return len; else { int max = 1; int start = 0; int end; int k; for (end = 1;end < len;++end) { for (k = start;k < end;++k) { if(s[end] == s[k]) { if((end - start) > max) max = end - start; start = k + 1; break; } } } if((end - start) > max) max = end - start; return max; }}
solution2：
int lengthOfLongestSubstring(string s) { int len = s.size(); if(len < 2) return len; else { int hash[256]; for (int i = 0;i < 256;++i) hash[i] = -1; int max = 1; int start = 0; int end = 1; hash[s[0]] = 0; while (end < len) { if (hash[s[end]] >= start) { if((end - start) > max) max = end - start; start = hash[s[end]] + 1; } hash[s[end]] = end; ++end; } if((end - start) > max) max = end - start; return max; } }
solution1是常规解法，solution2是优化算法。
solution2利用字符串中的字符和其对应的ascii码来建立哈希表，从而降低"在子串中查找重复字符"这一操作的复杂度。
详细解释请参考下文：http://blog.csdn.net/likecool21/article/details/10858799
Longest Substring Without Repeating Characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。