剑指OfferV2(增) -- 最长不含重复字符的子字符串
剑指OfferV2(增) -- 最长不含重复字符的子字符串
Part0前言
剑指Offer & LeetCode刷题仓库：
https://github.com/Damaer/CodeSolution文档地址：https://damaer.github.io/CodeSolution/刷题仓库介绍：刷题仓库：CodeSolution编程知识库：https://github.com/Damaer/Coding文档地址：https://damaer.github.io/Coding/#/剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~
Part1最长不含重复字符的子字符串
1题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围: 长度小于40000
示例1
输入："abcabcbb"
返回值：3
说明：因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例2
输入："bbbbb"
返回值：1
说明：因为无重复字符的最长子串是"b"，所以其长度为 1
示例3
输入："pwwkew"
返回值：3
说明：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
2思路 & 解答
这道题，可以使用哈希表解决，使用哈希表主要是为了保存字符最后一次出现的索引位置，同时记录开始索引位置start和最长的不包含 重复字符的子字符串长度len;
遍历每个字符，当发现map包含该字符的时候，如果该字符上次出现的位置不在``start之后，那么不用更新start,否则start`需要更新为上次出现该字符的位置。
遍历字符的时候，同时将每个字符以及它出现的索引位置，添加到map里面，计算当前的最长的不包含 重复字符的子字符串长度len，与之前保存的进行对比即可。
Java代码实现如下：
import java.util.HashMap;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
int lengthOfLongestSubstring(String s) {
int start = -1, len = 1;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
start = Math.max(start, map.get(s.charAt(i)));
}
map.put(s.charAt(i), i);
len = Math.max(len, i - start);
}
return len;
}
}
C++代码如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start = -1, len = 1;
unordered_map<char, int> myMap;
for (int i = 0; i < s.length(); i++) {
if (myMap.count(s[i]) > 0) {
start = max(start, myMap[s[i]]);
}
myMap[s[i]] = i;
len = max(len, i - start);
}
return len;
}
};
时间复杂度：遍历一次所有的字符，O(n)
空间复杂度：使用额外的空间map，故为O(n)
【作者简介】
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作
腾讯云开发者
