给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
解法1：超时
class Solution {
public int lengthOfLongestSubstring(String s) {
//假如使用动态规划,好像不太符合，因为动态规划无法判断当前字符同之前的字符是否相同。不同通过某种公式推导出来。
//ok，那现在就是看看笨的方法了,把字符串不同的记录下来
int maxResult = 0;
for(int i = 0 ; i < s.toCharArray().length; i++){
List<Character> charList = new ArrayList<>();
char ch = s.toCharArray()[i];
charList.add(ch);
for(int j = i+1; j < s.toCharArray().length; j++){
if(charList.contains(s.toCharArray()[j])){
break;
}
charList.add(s.toCharArray()[j]);
}
maxResult = Math.max(maxResult,charList.size());
}
return maxResult;
}
}解法2：
滑动窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
//什么是滑动窗口？
// 从第一个节点开始，计算到第几个节点才有不重复的数字
// 如果有重复的字符
Map<Character,Integer> map = new HashMap<>();
int maxLength = 0; //最大的长度
int leftIndex = 0; // 最左侧的值，用于记录当前索引值下，能够记录到的最长的无重复的子串
//
for(int i = 0; i < s.length(); i++){
//如果不包含此字符，那么在当前的最大长度就是索引值减 left
if(map.containsKey(s.charAt(i))){
//如果包含，则获取当前字符的索引值+1，使子串长度减少一位，然后看看是哪个的最左子串的索引位置值最大
leftIndex = Math.max(map.get(s.charAt(i))+1,leftIndex); //最左的字符需要跟当前字符串的索引位置比大小
}
maxLength = Math.max(maxLength,i-leftIndex+1);
map.put(s.charAt(i),i);
}
return maxLength;
}
}这样的话，时间复杂度就是O(n)
