给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
"abc"示例 2:
"b"示例 3:
"wke"
"pwke"提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0){
return 0;
}
Map<Character,Integer>map=new HashMap<>();
int max=0,left=0;
char[] c=s.toCharArray();
for(int i=0;i<s.length();i++){
if(map.containsKey(c[i])){
left=Math.max(left,map.get(c[i])+1);
}
max=Math.max(max,i-left+1);
map.put(c[i],i);
}
return max;
}
}这个算法的时间复杂度是O(n)，其中n是字符串的长度。因为它只需要遍历字符串一次，并且在HashMap中查找和更新操作的时间复杂度是O(1)。空间复杂度也是O(min(m, n))，其中m是字符集的大小，因为HashMap中最多只存储m个不同的字符。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 如果字符串为空，返回0
if(s.length()==0){
return 0;
}
// 使用HashMap来存储字符及其在字符串中的索引
Map<Character,Integer> map = new HashMap<>();
// 初始化最大长度为0，left指针为0
int max = 0, left = 0;
// 将字符串转换为字符数组
char[] c = s.toCharArray();
// 遍历字符串中的每个字符
for(int i = 0; i < s.length(); i++){
// 如果字符已经在map中，说明找到了重复的字符
if(map.containsKey(c[i])){
// 更新left指针，使其指向重复字符的下一个位置
// Math.max确保left指针不会向左移动
left = Math.max(left, map.get(c[i]) + 1);
}
// 更新最大长度
// i - left + 1表示当前无重复子串的长度
max = Math.max(max, i - left + 1);
// 将当前字符及其索引存入map
map.put(c[i], i);
}
// 返回最长无重复子串的长度
return max;
}
}
这段代码也是用来解决“最长无重复子串”问题的，不过它使用了一个数组来代替HashMap来记录字符上一次出现的位置。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 创建一个数组last，用来记录每个字符上一次出现的位置
// 数组大小为128，因为ASCII码表中有128个字符
int[] last = new int[128];
// 初始化数组，每个字符上一次出现的位置设为-1
for(int i = 0; i < 128; i++) {
last[i] = -1;
}
// 获取字符串长度
int n = s.length();
// 初始化结果为0，窗口开始位置为0
int res = 0;
int start = 0;
// 遍历字符串
for(int i = 0; i < n; i++) {
// 获取当前字符的ASCII码值
int index = s.charAt(i);
// 更新窗口开始位置，确保窗口内没有重复字符
// Math.max确保start不会向左移动
start = Math.max(start, last[index] + 1);
// 更新结果，计算当前无重复子串的长度
res = Math.max(res, i - start + 1);
// 更新当前字符最后出现的位置
last[index] = i;
}
// 返回最长无重复子串的长度
return res;
}
}
这个算法和之前使用HashMap的算法非常相似，但是它使用了一个固定大小的数组来记录字符最后出现的位置。由于数组的大小是固定的，因此空间复杂度是O(1)。算法的时间复杂度仍然是O(n)，因为它也是一次遍历字符串。
使用数组而不是HashMap可以节省空间，特别是当字符集不是很大时。然而，这种方法假设输入字符串只包含ASCII字符。如果字符串可能包含Unicode字符，那么需要使用更大的数组或者回到使用HashMap的方法。
