前言
如果你能找到这里，真是我的幸运~这里是蓝白绛的学习笔记，本集合主要针对LeetCode。这里我会记录刷leetcode的学习和思考的过程，如果和leetcode官方解题有雷同，那是当然会有的啦。我会在记录的同时配以图文解释，如果对大家有帮助，那就再好不过了。
题目
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例：（具体可在leetcode中查看）
input：abcabcbb
output：3
思路
暴力破解
首先我们需要i和j用两层嵌套循环来遍历所有子串。对于每个子串，我们需要判断子串中是否有重复，也就是需要遍历该子串，那么这个时间复杂度是。
滑动窗口
滑动窗口是数组/字符串问题中常用的抽象概念。i和j代表下标，表示数组中
到
的元素。开闭可自定义，但一般前闭后开。在此题中，如果从
到
的子字符串
没有重复，那么我们只需要检查
对应的字符是否已经在
中。我们用HashSet构造一个滑动窗口，将当前无重复的字符存在HashSet中。如果在hashset中，则
++，子串长-1，ans不动；如果不在hashset中，则
++，子串长+1，ans更新。此题只需要用更大的ans改写之前的ans就行，不需要输出最长的无重复子串是什么，用hashset没问题。附代码和图解如下。时间复杂度为
。
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int i = 0;
int j = 0;
int ans = 0;
while(i<s.length() && j<s.length()){
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j));
j += 1;
ans = Math.max(ans, set.size());
}else{
set.remove(s.charAt(i));
i += 1;
}
}
return ans;
}
}
优化的滑动窗口
上面滑动窗口的方法要不停的增加元素和移除元素，虽然我们已经利用hashset使增加元素和移除元素的时间复杂度尽可能低，但是我们还有方法可以加速。如果我们遇到一个重复的元素，则可直接跳转到当前子串中重复元素的后一位，这在重复元素在子串中间时特别高效。优化的滑动窗口利用hashmap存储当前最长子串，并且不需要删除元素。当j增加一位的时候，我们检查
是否在hashmap中，并查找map中对应的value值即可判断是否重复，如果重复，则
跳转到value+1。这里的一个关键问题是，我们不删除hashmap中的元素，如何判断遇到的新元素是否已经在当前最长子串中？这里非常欣赏leetcode官网的解答，代码如下。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
//关键步骤，hashmap如何判断是否有重复。
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
这句代码的意思是如果在map中，获得
对应的value值，如果value值小于当前i，则表示
并未重复。大家可以好好体会这段代码，图解见下图。
小结
这是我刚开始在leetcode上刷题，所以参考了leetcode的官方解法，时间有限就不看更多解法了。这里官方解法中的hashmap解法个人认为非常精彩，对于实现滑动窗口有非常好的优化。
结尾
如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的图文，请点喜欢~*我是蓝白绛，感谢你的阅读！
