一.前言
今天遇到了这种找出无重复字符的最长子串的算法题，小编思来想去依旧没有想到有什么好方法，直到看到了大佬的算法，极为震撼，想写篇博客，记录下来。
题目如下：给出一组字符串，如 s = “ adsjkhf ”，返回值为7，s = “abb”，返回值为2，s = “aab”，返回值为2。请判断此字符串中无重复字符的最长子串。
二.补充
Java HashMap中的方法：
get() 方法获取指定 key 对应对 value：map.get(key)
put() 方法将指定的键/值对插入到 HashMap 中：map.put(key,value)
containsKey()方法如果 map 中存在指定的 key 对应的映射关系返回 true，否则返回 false。
三.题解
本题主要通过滑动窗口的思想解决。那么什么是滑动窗口呢？其实就是类似于两个前后指针，两个指针不断向后移，我们只关注指针中间的数，最后返回指针中间的元素的个数。
(1) 分析
我们先定义一个map容器用于存放字符串中的每个字符，然后从字符串的第一个字符a开始（ i = 0 ）开始找，此时map里面是没有这个元素的，因此我们把a存放进map中，继续执行此操作直到出现map中有相同的字符，此时只需把left指针指向相同元素的后一位，两个指针中间的部分就是不重复字符的子串，此时这个子串的长度就为i - left + 1。我们只需要用这个方法往后看去（随着i增加，即后指针向后指去），寻找是否有比当前子串长度更大的，若遇到则将现在的长度替换即可。
注意：字符串可能是这样的 --> “ abbac”。按照我们的方法，会先将ab存入到我们的map当中，此时left = 0，当i=2时，由于map中已经有b，因此left将等于get(b) + 1 = 2。随后i指针向后指去又遇到map已有元素a，按照前面的算法，此刻left = get(a) + 1 = 1,但实际上left不会变，仍然等于2，因此在求left值时总应该取最大的那个。
(2) 代码详解
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;//记录最长的的无重复字符串的长度
int left = 0;//前指针
HashMap<Character,Integer> map = new HashMap<>();
for (int i=0;i<s.length();i++){
if (map.containsKey(s.charAt(i))){ //若map中有此元素则执行下面代码
left = Math.max(left,map.get(s.charAt(i))+1); //上面已经解释，此处应一直取较大的left
}
map.put(s.charAt(i),i); //将s中的第i个元素存入map中
maxLen = Math.max(maxLen,i -left + 1); //maxLen即为两个指针中间的元素个数
}
return maxLen;
}
(3) 图解
最初left=0，i=0，map中无任何元素，此时map中将添加a字符
此时i=1，map中将添加b字符
此时i=2，map中将添加c字符
此时i=3，检测到map中已有a，left将指向到map中的a的后一位b
以此类推遍历完字符串直到 i = s.length()，返回最后的maxLen即为最终答案。
网友评论