首页 > 代码库 > [LeetCode] Longest Substring Without Repeating Characters最长无重复子串
[LeetCode] 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.
Hide Tags
Hash Table Two Pointers String 这题有前面的基础其实很简单的，http://www.cnblogs.com/Azhu/p/4127606.html
思路类似，使用双索引表示目标的头尾，左索引指向能去的第一个，右索引指向不取的第一个，那么初始化均为0，长度就是右-左，两者相等表示子串为空。
注意：
- 子串与子序列不同，子串是需要连续的，子序列只要求顺序，不要求连续。
- 表示好子串（窗口）很重要，确认清楚索引指向是否在窗口内。
- 因为需要标记字符，所以直观想到的是hash_map or unordered_map，不过基于AscII 只要一个128 位的bool 数组，discuss 他们声明为256，不过用128通过了。
- 数组下标如果直接使用字符好像隐式转换失败，需要加上强制转换。
算法实现：
- 初始化窗口索引lft=rgt=0,同时初始化标记数组，表示那个一个字符是否在窗口内。
- 右索引遍历字符串
- 如果遇到不在窗口内的字符rgt+1，改变flag，计算更新最长子串长度。
- 如果在窗口内，lft+1，修改flag，重新判断rgt 位置的字符。
我写的代码：
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 5 class Solution { 6 public: 7 int lengthOfLongestSubstring(string s) { 8 int n = s.length(); 9 if(n<2) return n ;10 int lft = 0,rgt =0,maxlen = 0;11 bool sign[128] = {false};12 while(rgt<n){13 // cout<<lft<<" "<<rgt<<" "<<maxlen<<endl;14 if(sign[(int)s[rgt]]==false){15 sign[(int)s[rgt]]=true;16 rgt++;17 if(maxlen<rgt-lft) maxlen = rgt - lft;18 continue;19 }20 sign[(int)s[lft]] = false;21 lft++;22 }23 return maxlen;24 }25 };26 27 int main()28 {29 string s= "242522f23r23rt432twrfs122";30 Solution sol;31 cout<<sol.lengthOfLongestSubstring(s)<<endl;32 return 0;33 }
[LeetCode] Longest Substring Without Repeating Characters最长无重复子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。