题目描述
找出一个字符串中不含有重复字符的最长子串的长度。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
解析
算法技巧：
应用HashMap存储遍历的字符及其坐标索引，以减少遍历字符串次数，利用空间换取时间
实现方法：
方法一：暴力法依次遍历字符串中每个字符作为开头的最长子串，在众多子串中选出最长子串。
方法二：在方法一基础上每次查找新的字符开头的子串时，记录已经存在的字符，这样可以消除为判断是否重复而往回校验的时间消耗。
方法三：遍历一趟字符串，并且不走回头路。需要记录子串开始的位置head，和HashMap记录已经存在的字符，如果遇到当前字符已经存在则统计当前的最长子串，head不需要移动到1，而是移动到重复字符的后一位。例如，s[j]在s[i]~s[j-1]存在，下标为k（i <= k <= j-1 ），则新的子串从k + 1开始即可，因为i与k之间开头的字符不可能存在长度超过j-i的不重复子串。同时，考虑一种特殊情况，如果HashMap中存在当前字符，但是当前字符却不在遍历的区间，那么此时head不需要移动，但是要更新HashMap。
代码
public int lengthOfLongestSubstring(String s) {
int head = 0, tail = head, longest = 0;
Map<Character, Integer> map = new HashMap<>();
while(tail < s.length()){
char c = s.charAt(tail);
Integer i = map.get(c);
if(i != null){//HashMap存在当前字符c
longest = (tail - head) > longest ? (tail - head) : longest;//遇到重复时更新最长子串长度
head = head > i ? head : i + 1;//判断是否在当前区间内，决定是否改变head
}
map.put(c, tail);//新插入或者更新HashMap
tail++;
}
return (tail - head) > longest ? (tail - head) : longest;
}
