网站ip段屏蔽,农林网站建设公司,加强公司门户网站建设方案,长春市做网站题目链接#xff1a;
3. 无重复字符的最长子串 - 力扣#xff08;LeetCode#xff09; 题目的要求是让我们找到字符串中的最长字符串#xff0c;这个很显然我们首先想到暴力解法#xff0c;列举所有的字符串找到不重复的#xff0c;我们在此思路上优化算法进行滑动窗口的…题目链接
3. 无重复字符的最长子串 - 力扣LeetCode 题目的要求是让我们找到字符串中的最长字符串这个很显然我们首先想到暴力解法列举所有的字符串找到不重复的我们在此思路上优化算法进行滑动窗口的优化。
首先先来一下暴力解法直接枚举所有的字符串
先来枚举所有的子字符串然后利用map进行判断是否有重复字符串进行长度的计算。
求得最大的len。显然结果超时。 int lengthOfLongestSubstring(string s) {vectorstring substrings;int n s.length();for (int i 0; i n; i) { // 起始位置for (int j 1; j n - i; j) { // 子串长度substrings.push_back(s.substr(i, j));}}int len0;for(auto e:substrings){mapchar,intnum;for(auto b:e){num[b];if(num[b]1)break;else{len max(len, (int)num.size());}}}return len;}
滑动窗口的基本思路是
两个指针利用下标访问用Int代替指针开始的时候都指向开头用map记录每个字符出现的次数当次数大于1时我们进行计算一次长度取最大长度让left移动到窗口内无重复字符串吗继续滑动。
细节问题
这里有个细节问题是当我们的right滑出字符串时我们会少计算一次长度导致错误所以我们每次结束之后计算一次最后的left位置到right为止的字符串长度即可。
下面给出滑动窗口的代码
class Solution {
public:int lengthOfLongestSubstring(string s) {int left0;int right0;mapchar,intnum;int len0;for( right0;rights.size();right){num[s[right]];//当map内某个字符出现次数大于1if(num[s[right]]1){//计算一次长度lenmax(len,right-left);//让left移动到窗口内无重复字符串while(s[left]!s[right]){num[s[left]]--;left;}num[s[left]]--;left;}} lenmax(len,right-left);if(len0)lens.size();return len;}
};
