[LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2870字，纯文字阅读大概需要5分钟。
内容图文
1.暴力法：
本题让求给定字符串的最长的无重复字符的子串，首先想到暴力解法，穷举出字符串的所有子串，并判断每个子串是否是不重复子串，具体使用hashset或set判是否有重复字符；暴力法效率很差，时间O(n^3)，空间O(n);参考代码如下：
1
class
Solution {
2
public
:
3
int lengthOfLongestSubstring(string s){
4int res = 0;
5constint size = s.size();
6if(s.empty()) return0;
7if(size<=1) return size;
8for(int i = 0;i<size;++i)
9for(int j = i;j<size;++j)
10 {
11int sub_seq = j-i+1;
12if(isNoreapeatSubstring(i,j,s)){
13if(sub_seq>=res)
14 res = sub_seq;
15 }
16 }
17return res;
18 }
1920bool isNoreapeatSubstring(int l,int h,string &s)
21 {
22set<char> charSet;
23for(int i =l;i<=h;i++)
24 {
25if(charSet.find(s[i])==charSet.end())
26 {
27 charSet.insert(s[i]);
28 }
29else{
30returnfalse;
31 }
32 }
33returntrue;
34 }
35 };
2.动态规划
稍加思考，很容易发现本题是一个具有最优子结构的最优解问题，所以可以用动态规划的方法；
2.1 定义状态
dp[i]: 字符串s中，以字符s[i]结尾的最长的不重复子串的长度；
2.2 转态转移 （方程）
当s[i]和以s[i-1]结尾的最长不重复子串中所有的字符都不相同时，dp[i] = dp[i-1]+1;否则，找以s[i-1]结尾的最长不重复子串中和s[i]重复的最后的字符位置index，则
dp[i]=i-1-index+1; 动态规划的时间O(n^2),空间O(n^2);
参考代码如下：
1
class
Solution {
2
public
:
3
int lengthOfLongestSubstring(string s) {
4constint size = s.size();
5if(s.empty()) return0;
6if(size<=1) return size;
7int dp[size];//dp[i]表示以s[i]结尾的不重复子串 8 memset(dp,0,size);
9int res = 1;
10 dp[0]=1;//dp初始值11for(int i = 1;i<size;++i)
12 {
13bool reapeat = false;
14int index = 0;
15for(int j = i-1;j>= i-1-dp[i-1]+1;j--)
16 {
17if(s[j]==s[i])
18 {
19 reapeat = true;
20 index = j ;//最近的一次重复21break;
22 }
23 }
24if(reapeat)//重复25 {
26 dp[i]=i-1-index+1;
27 }
28else//不重复29 {
30 dp[i]=dp[i-1]+1;
31 }
32if(dp[i]>=res)
33 res=dp[i];
34 }
35return res;
36 }
37 };
3.滑动窗口+hash表 法
可以在遍历字符串 的过程中维护一个滑动窗口，使得滑动窗口内的子串表示字符串的当前最长不重复子串，具体地，使用hashmap m记录字符串中字符和其最后一次出现的位置之间的映射；定义变量left，res,left表示滑动窗口的左边界的前一个位置，初始化为-1，res表示滑动窗口的长度最大值；
遍历到一个字符s[i]时，如果字符在hashmap中，且最后一次的位置在滑动窗口内（i>left）,将滑动窗口的边界右移，left = m[s[i]];然后更新hash表,
使用滑动窗口+hash表的方法可以实现最好的效率,因为只需遍历一遍，所以时间O（n）,因为字符的个数是一定的（最多128个）所有空间O(1),
class
Solution {
public
:
int lengthOfLongestSubstring(string s) {
int res = 0,left = -1,str_len=s.size();//
unordered_map<int,int> m;//映射字符中字符和其最后一次出现的位置for(int i = 0;i< str_len;++i)
{
if(m.count(s[i])&&m[s[i]]>left){
left = m[s[i]];
}
m[s[i]] = i;//更新字符最后一次出现的位置
res = max(res,i-left);
}
return res;
}
};
下面这种写法是上面解法的精简模式，这里我们可以建立一个 256 位大小的整型数组来代替 HashMap，这样做的原因是 ASCII 表共能表示 256 个字符，但是由于键盘只能表示 128 个字符，所以用 128 也行，然后全部初始化为 -1，这样的好处是不用像之前的 HashMap 一样要查找当前字符是否存在映射对了，对于每一个遍历到的字符，直接用其在数组中的值来更新 left，因为默认是 -1，而 left 初始化也是 -1，所以并不会产生错误，这样就省了 if 判断的步骤，其余思路都一样：
class
Solution {
public
:
int lengthOfLongestSubstring(string s) {
vector<int> m(128, -1);
int res = 0, left = -1;
for (int i = 0; i < s.size(); ++i) {
left = max(left, m[s[i]]);
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
原文：https://www.cnblogs.com/wangxf2019/p/12160641.html
内容总结
以上是互联网集市为您收集整理的[LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串全部内容，希望文章能够帮你解决[LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。