无重复字符的最长子串
解决方法：滑动窗口
解题步骤：
步骤1：
- 首先定义两个指针fast和low，fast表示窗口的左边，low表示窗口的右边，初始状态均置为0
- 定义dis变量用来记录当前窗口的大小，res记录最终的结果，
- 定义数组arr记录每一个字符出现的最后位置，初始化为-1
步骤2：
- low指针依次向后移动，每次判断low指针指向的字符上一次出现的位置是否在fast和low之间
- 如果不在，更新该字符最后出现的位置，窗口的大小增1
- 如果在即出现了重复的字符，首先计算当前窗口的大小，判断是否需要更当前窗口的大小；然后更新fast指针（让该指针指向重复字符上一次出现的下一个位置）；最后更新窗口的大小和low指针指向的字符最后一次出现的位置。
代码：
//测试代码
public class Main{
public static void main(String[] args) {
String s = "abcabcbb";
System.out.println(new Solution().lengthOfLongestSubstring(s));
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0){
return 0;
}
int[] arr = new int[255];
int fast = 0, low = 0; //fast表示窗口的起始位置，low表示末尾位置
int dis = 0, res = 0; //dis记录当前窗口的大小，res记录最终的结果
for(int i = 0; i < arr.length; ++i){
arr[i] = -1;
}
//low指针一直向后进行移动
while(low < s.length()){
//如果当前字符未在窗口内出现，修改该字符最后出现位置的，然后将出口的大小加1
if(arr[s.charAt(low)] < fast){
arr[s.charAt(low)] = low;
++dis;
} else { //如果出现，更新结果，并修改窗口的起始位置，同时更新窗口的大小
if(dis > res){
res = dis;
}
fast = arr[s.charAt(low)] + 1;
dis = low - fast + 1;
arr[s.charAt(low)] = low;
}
++low;
}
if(dis > res){
res = dis;
}
return res;
}
}
查看29道真题和解析