网站建设成本 网站空间/全国最新疫情最新消息

1，算法介绍

输入一个字符串，求这个字符串中存在最大不重复子串的长度，

例如

• 输入 abcdabcbb，最大不重复子串 abc ，即输出 3;

• 输入 bbbbbbb，最大不重复子串 b，即输出 1;

• 输入pwwkew ，最大不重复子串 kew，即输出 3；

2，算法思想

利用滑动窗口思想解题，创建一个字符c串容器 记作B，来存放找到的最大不重复子串；利用 递归循环来对原字符串字符进行逐个搜索，搜索过程中存在两种情况发生

• 如果当前搜索到的字符 a 不存在 B 中，则将字符 a 插入B 后面；
• 如果字符 a 存在 B 中则进行 While 循环 ，不断从 B 的左端不断删除字符，直到 B 中不包含字符a 即可，此时计算一下字符串 B 的长度；

最后计算过程中求字符串B 长度的最大值即可

3，代码实现（C++）

class Solution {
public:int lengthOfLongestSubstring(string s) {if (s.size()!=0){unordered_set<char> lookup;//创建一个无序容器；int maxStr = 0;int left = 0;for (int i= 0;i<s.size();i++){while(lookup.find(s[i])!= lookup.end()){lookup.erase(s[left]);//删除元素left++;}maxStr = max(maxStr,i-left+1);lookup.insert(s[i]);}return maxStr;}else{return 0;}}
};

这里创建一个 loookup(unordered_set 类型)来存放 最大不重复子串；

while 循环模块用来处理,搜索到的字符存在最大不重复子串中情况；从最大不重复子串左端开始，对元素逐个删除，直至查询不到为止；

while(lookup.find(s[i])!= lookup.end())
{lookup.erase(s[left]);//删除元素left++;
}