题目描述
请从字符串中找出⼀个最⻓的不包含重复字符的⼦字符串，计算该最⻓⼦字符串的⻓度。
数据范围: ⻓度⼩于40000
示例1
输⼊："abcabcbb"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是"abc"，所以其⻓度为 3。
示例2
输⼊："bbbbb"
返回值：1
说明：因为⽆重复字符的最⻓⼦串是"b"，所以其⻓度为 1
示例3
输⼊："pwwkew"
返回值：3
说明：因为⽆重复字符的最⻓⼦串是 "wke"，所以其⻓度为 3。
思路及解答
这道题，可以使⽤哈希表解决，使⽤哈希表主要是为了保存字符最后⼀次出现的索引位置，同时记录开始索引位置 start 和最⻓的不包含 重复字符的⼦字符串⻓度 len ;
遍历每个字符，当发现 map 包含该字符的时候，如果该字符上次出现的位置不在 start 之后，那么不⽤更新 start ,否则 start 需要更新为上次出现该字符的位置。
遍历字符的时候，同时将每个字符以及它出现的索引位置，添加到 map ⾥⾯，计算当前的最⻓的不包含重复字符的⼦字符串⻓度 len ，与之前保存的进⾏对⽐即可。
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;
}
}- 时间复杂度：遍历⼀次所有的字符，O(n)
- 空间复杂度：使⽤额外的空间 map ，故为O(n)