查找一个字符串中最长不含重复字符的子字符串，计算该最长子字符串的长度
算法题：查找一个字符串中最长不含重复字符的子字符串，计算该最长子字符串的长度；
下面将使用 滑动窗口 方法实现，并通过对滑动窗口算法一步步进行优化，使其空间和时间的消耗一步步降低；
什么是滑动窗口？
滑动窗口：一般是指 运行在一个大数组上的子数组，该大数组是一个底层元素集合 。
例如：假设有大数组 [ a b c d b e f d n ] ，设定一个大小为 3 的小数组 为 滑动窗口 ；则存在下面的窗口：
[a b c]
[b c d]
[c d b]
[d b e]
[b e f]
[e f d]
[f d n]
滑动窗口重要性质：
- 滑动窗口一般表示成一个 左闭右开区间 。
- 窗口的左边界（指针 i）和右边界（指针 j）永远只能向右移动 ，而不能向左移动。
如图：
使用滑动窗口解题
1、未优化的滑动窗口实现：
没有任何优化的滑动窗口实现；
通过 指针 i 和 指针 j 不断的向左移动，形成了一个个的窗口，并且在将窗口的字符存放到了 Set 集合中，使用 Set 集合判断 即将 进入窗口中的字符（也就是指针 j 移动到指向的字符）是否在窗口已经存在；
- 如果已经存在：则计算此时窗口的大小，并将存放窗口字符的 Set 集合清空（清空是为了存放下个窗口的字符），最后将 指针 i 向左移动一位，然后指针 j 也指向指针 i 的位置。
- 如果是不存在：则将此字符存放到 Set 集合窗口字符中 。
1.1、看图理解：
1.2、代码实现：
public class LeetCode {
public static int lengthOfLongestSubstring(String s) {
if (s == null){
return 0;
}
if (s.length() == 1){
return 1;
}
// set 用来存储窗口的字符
Set set = new HashSet();
// 指针i
int i = 0;
// 指针j
int j = i;
// 最大长度
int max = 0;
char[] sc = s.toCharArray();
while(j < sc.length && i <= j){
// 当字符没在窗口中
if (!set.contains(sc[j])){
set.add(sc[j]);
// 指针j 移动
j++;
}else {
// 如果字符在窗口中时, 得到当前窗口中的字符个数
int size = set.size();
if (max max){
max = set.size();
set.clear();
set = null; // help GC
}
return max;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcdbefdn"));
}
}
1.3、执行效果（来自LeetCode）：
1.4、未经优化的滑动窗口的缺点：
缺点一：
存在很多无用的重复的 滑动窗口 ；
例如：字符串 abcdbefdn，根据上面实现的滑动窗口方法，会得到以下窗口：[ a b c d ]、[ b c d ]、[ c d b e f ]、[ d b e f ]、[ b e f d n ] 这 5 个滑动窗口；下面错位展示更直观，会发现 [ b c d ]、 [ d b e f ] 这两个滑动窗口显然被包含在其之前的窗口中，它们被重复统计了。
[ a b c d ]
[ b c d ]
[ c d b e f ]
[ d b e f ]
[ b e f d n ]
缺点二：
存储 滑动窗口中 字符的 Set 集合存在反复 清空，再次存入字符的情况；并且存在字符被重复存入 Set 集合中。
2、优化后的滑动窗口实现：
优化点：
-
直接将指针 i 指向出现的重复字符的位置，滑动窗口大小为 （j – i），这样就将无用的重复的 滑动窗口 跳过，这样会大大缩短执行时间；
-
存放滑动窗口的字符容器改为 Map 集合，key为 字符，value 为字符下标；并且不再清空集合了，而是遇到重复字符后，更新此字符的下标位置；
例如：一开始 字符 b 在map集合中的value 位置为1，当再次遇到下标为 3 的字符 b 后，将map集合中的value 下标 由 1 改为 3 ；
2.1、看图理解：
2.2、代码实现：
public class LeetCode {
public static int lengthOfLongestSubstring(String s) {
if (s == null){
return 0;
}
if (s.length() == 1){
return 1;
}
// map 用来存储窗口字符, key是字符, value为字符在字符串中的下标位置
Map map = new HashMap();
// 指针j
int j = 0;
// 重复字符的位置, 默认为-1
int i = -1;
// 最大长度
int max = 0;
char[] sc = s.toCharArray();
while(j i){
i = index;
}
}
// 指着j - 重复字符的位置 = 当前窗口的大小
if ((j-i) > max){
max = j-i;
}
// 如果map中存在重复字符的话,这里是将字符的位置进行更新 ; 如果不是重复字符的话，就直接存放到map中
map.put(sc[j], j);
j++;
}
map.clear();
map = null; // help GC
return max;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcdbefdn"));
}
}
2.3、执行效果（来自LeetCode）：
上面就是经过了代码优化后得到的执行效果，发现执行时间大大缩短了；但是这可能还不是最优的，可能还存在最优的方法。
❤不要忘记留下你学习的足迹 [点赞 + 收藏 + 评论]嘿嘿ヾ
一切看文章不点赞都是“耍流氓”，嘿嘿ヾ(◍°∇°◍)ﾉﾞ！开个玩笑，动一动你的小手，点赞就完事了，你每个人出一份力量(点赞 + 评论)就会让更多的学习者加入进来！非常感谢！￣ω￣=
About The Author
