难度：中等
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
第一种解答：
思路：
使用一个长度为 128 的 boolean 数组 flag 充当散列表用来记录子串的字符（利用到字符的 ascii 码作为数组的下标），初始化都为false。遍历整个字符串，外循环控制子串的起始，内循环控制子串的长度，每遇到一个字符就检查 flag 中是否存在该元素，不存在则将 flag[]设置为 true，存在则结束内循环。
class Solution {
public int lengthOfLongestSubstring(String s) {
boolean[] flag = new boolean[128]; // 问题1
int sublen = 0;
for(int i = 0; i < s.length(); i ++){
// 将 flag 初始化为 false
for(int k = 0; k < flag.length; k++)
flag[k] = false;
// 子串的起始
flag[(int)(s.charAt(i))] = true;
int len = 1;
for(int j = i+1; j < s.length(); j ++){
// flag 中存在相同字符的情况
if(flag[(int)(s.charAt(j))])
break;
// flag不存在相同字符的情况
len ++;
flag[(int)(s.charAt(j))] = true;
}
if(sublen < len){
sublen = len;
}
}
return sublen;
}
}
也可将 boolean 数组换成 int 数组，数组记录的是元素所在的下标。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.equals("")) return 0;
int[] flag = new int[128];
int sublen = 0 ,len;
for(int i = 0; i < s.length(); i ++ ){
// 初始化 flag;
for(int k = 0; k < flag.length; k++)
flag[k] = -1;
flag[s.charAt(i)] = i;
len = 1;
for(int j = i + 1; j < s.length(); j ++){
if(flag[s.charAt(j)] != -1){
i = flag[s.charAt(j)];
break;
}
len ++;
flag[s.charAt(j)] = j;
}
sublen = len > sublen ? len: sublen;
}
return sublen;
}
}
参考评论区的第二种解答
第二种解答：
使用双指针 left, right维护一个无重复字符区间（left 与 right 之间的字符无重复），right 指针每移动到一位，就循环检测 [left , right) 无重复字符区间是否存在与 right指向的字符相同的字符，如果存在就更新 left 指针，将 left移动到区间中与right指向相同字符的下一个位置，继续维护一个无重复的字符区间，同时更新最长子串的长度max。不存在则更新最长子串的长度max，同时继续将 right 往下移动。
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0, left = 0, right = 0;
if(s.length() == 1)
max = 1;
else if( !s.equals("") ){
//char[] str = s.toCharArray();
for(right = 1; right < s.length(); right ++){
for(int i = left; i < right; i ++){
if(s.charAt(i) == s.charAt(right)){
// 更新 max
max = right - left > max ? right - left : max;
left = i + 1;
break;
}
}
// 更新 max
max = right- left + 1 > max ? right - left + 1: max;
}
}
return max;
}
}
