网站的动态图怎么做的,小程序招商,企业宣传注册哪些论坛 网站好,wordpress缓存文章页1. 题目
给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。示例 2:
输入: bbbbb
输出: 1
解释: 因为无重…1. 题目
给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。示例 2:
输入: bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:
输入: pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
《剑指Offer》同题面试题48. 最长不含重复字符的子字符串
2. 哈希解题
设置startend窗口检查字符在哈希表中吗不在插入表中value为下标在表中则删除start到重复的那个位置的hash表中的key更新窗口和maxlen
class Solution {
public:int lengthOfLongestSubstring(string s) {int i, j, k, start 0, end 0, maxlen 0;unordered_mapchar,int m;unordered_mapchar,int::iterator it;for(i 0; i s.size(); i){it m.find(s[i]);if(it ! m.end()){k it-second;for(j start; j k; j) //之前没用k存储erase后it失效m.erase(s[j]);start k1;}m[s[i]] i;end;if(end-start maxlen)maxlen end-start;}return maxlen;}
};优化写法
class Solution {
public:int lengthOfLongestSubstring(string s) {int i, k, start 0, end 0, maxlen 0;unordered_mapchar,int m;unordered_mapchar,int::iterator it;for(i 0; i s.size(); i){it m.find(s[i]);if(it ! m.end()){k it-second;start max(start, k1);//不删keystart直接跳到重复的下一个}m[s[i]] i;//更新下标位置end;if(end-start maxlen)maxlen end-start;}return maxlen;}
};class Solution { //2020.3.10
public:int lengthOfLongestSubstring(string s) {if(s.empty())return 0;setchar set;int i 0, j 0, maxlen 0;for( ; j s.size(); j){if(!set.count(s[j])){set.insert(s[j]);maxlen max(maxlen,j-i1);}else{while(s[i] ! s[j]){set.erase(s[i]);}i;}}return maxlen;}
};class Solution { //2020.5.2
public:int lengthOfLongestSubstring(string s) {unordered_mapchar,int m;int maxlen 0, i 0, j 0;while(j s.size()){m[s[j]];if(m[s[j]]1){while(m[s[j]]1){m[s[i]]--;i;}}elsemaxlen max(maxlen,j-i1);j;}return maxlen;}
};
