无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=3
解题思路分析：
本题是一道双指针题目，类似的题目在Leetcode中有很多，比如 LEETCODE 340. Longest Substring with At Most K Distinct Characters 解题思路分析。那一题也是求最大连续无重复字串长度，但是不重复的字符个数最多只能有k个。而本题没有k的限制，只要只要字串中没有重复字符即可。
首先我们定义2个指针，左指针和右指针初始位置都在0，然后再定义一个Map，来存储当前区间（左指针到右指针范围）内每种字符出现的次数。开始先移动右指针，查看当前右指针指向的字符，如果该字符之前出现过0次，说明当前字符是首次出现，即当前区间内不存在重复字符，此时区间长度为一个合理解，用当前合理解更新全局最大合理区间长度。反之，如果当前字符之前已经出现过1次，那么说明当前出现了重复字符，此时区间为不合理区间，这时开始移动左指针，查看左指针指向的字符，如果该字符之前出现过1次，左指针划过该字符下标，该字符从区间内被移出，区间内出现次数减一（变为0），继续移动左指针，如果当前字符出现次数为2，说明当前字符原先是重复字符，移除该字符后，该字符变成唯一，此时区间又变为合理区间，结束移动左指针，返回继续移动右指针。直到右指针到达字符串尾部，结束循环。
实现代码：
public int lengthOfLongestSubstring(String s) {
// 为了提高效率，将字符串转为字符数组
char[] arr = s.toCharArray();
// 记录区间内每种字符出现个数
Map<Character,Integer> map = new HashMap<>();
// 左右2指针
int left=0,right=0;
// 返回结果
int res=0;
// 循环右指针
while(right<s.length()){
// 查看当前右指针指向字符在区间内出现个数
int countRight = map.getOrDefault(arr[right], 0);
// 将个数加一保存至map
map.put(arr[right], countRight+1);
// 如果之前该字符出现个数为0，
// 说明当前该字符为首次出现，区间内不包含重复字符
// 当前区间为合理区间
if(countRight==0) {
// 更新全局合理区间最大长度
res=Math.max(res, right-left+1);
} else{ // 如果当前字符在区间内出现过
while(left<=right){
// 移动左指针，查看左指针指向的字符个数
int countLeft = map.get(arr[left]);
// 将字符个数减一保存至map
map.put(arr[left], countLeft-1);
// 移动左指针
left++;
// 如果该字符原先出现过2次，即重复字符，
// 移除一个该字符后，该字符变为唯一，区间变为合理
// 结束移动左指针，返回移动右指针
if(countLeft==2) break;
}
}
right++;
}
return res;
} 本题解法执行时间为11ms。
Runtime: 11 ms, faster than 34.06% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 46.6 MB, less than 5.20% of Java online submissions for Longest Substring Without Repeating Characters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-3-longest-substring-without-repeating-characters/