请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：dp
dp[i]表示以s[i]结尾的最长不重复子串的长度
设dp[i-1]=k
如果在s[i-k]....s[i-1]中都不存在s[i]，dp[i]=dp[i-1]+1
如果在s[i-k]....s[i-1]中存在s[j]=s[i]，dp[i]=i-j
在遍历过程中用一个变量max记录整个串不重复子串的最大长度
判断s[i-k]....s[i-1]中存不存在s[j]=s[i]，需要再往前搜索
public int lengthOfLongestSubstring(String s) {
if(s==null||s.equals("")){
return 0;
}
int[] dp=new int[s.length()];
dp[0]=1;
int max=1;
for (int i = 1; i < dp.length; i++) {
for (int j = i-1; j >=i-dp[i-1] ; j--) {
if(s.charAt(i)==s.charAt(j)){
dp[i]=i-j;
break;
}
if(j==i-dp[i-1]){
dp[i]=dp[i-1]+1;
}
}
max=Math.max(max,dp[i]);
}
return max;
}
时间复杂度O(n2)，空间复杂度O(n)
优化：
时间：采用哈希表，用来记录字符在串中最后出现的位置，可以避免向前搜索
空间：不需要dp数组，只需要用一个变量记录上一个位置的最大长度
public int lengthOfLongestSubstring(String s) {
if(s==null||s.equals("")){
return 0;
}
int[] map=new int[128];
Arrays.fill(map,-1);//-1表示未出现
map[s.charAt(0)]=0;
int max=1;
int temp=1;//前一个位置最大长度
for (int i = 1; i < s.length(); i++) {
int index=map[s.charAt(i)];
map[s.charAt(i)]=i;//记录或更新位置
if(index==-1){
temp++;//由于字符还没有出现过，当前长度可以根据上一个位置的长度加1
} else {
if(temp<i-index){
temp++;//相当于字符上次出现的位置不在搜索的范围内，直接加1就是，考虑abba 最后一个a的位置
} else {
temp=i-index;
}
}
max=Math.max(max,temp);
}
return max;
}
时间复杂的O(n)，空间复杂度O(1)
滑动窗口（双指针法）
滑动窗口中维护着不重复的子串，滑动窗口的长度即为不重复子串的长度
两个指针low,high，分别表示滑动窗口的开始和结束位置
每次循环high++
如果在滑动窗口中出现了s[high]，找到s[high]最后出现的位置j，并将low=j+1
如果在滑动窗口中没有出现s[high]，一切正常
在遍历过程中不断更新最大长度
public int lengthOfLongestSubstring(String s) {
if(s==null||s.equals("")){
return 0;
}
int max=1;
int low=0;
int high=1;
while (high<s.length()){
int index = s.substring(low, high).lastIndexOf(s.charAt(high));
if(index>=0){
low+=index+1;
}
high++;
max=Math.max(max,high-low);
}
return max;
}
时间复杂度O(n2)，空间复杂度O(1)
用哈希表优化滑动窗口
public int lengthOfLongestSubstring(String s) {
if(s==null||s.equals("")){
return 0;
}
int max=1;
int low=0;
int high=1;
int[] map=new int[128];
Arrays.fill(map,-1);
map[s.charAt(0)]=0;
while (high<s.length()){
int index = map[s.charAt(high)];
map[s.charAt(high)]=high;
if(index>=0){
low=Math.max(low,index+1);
}
high++;
max=Math.max(max,high-low);
}
return max;
}
时间复杂的O(n)，空间复杂度O(1)
