3. 无重复字符的最长子串
leetcode题目链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
解题思路： 这道题同167号问题一样，使用滑动窗口的思路解决。依旧是我的excel图，献丑了。。。
就拿上述例子pwwkew来举例。定义左右两个指针，分别l=0，r=-1，此时[l…r]为滑动窗口，不包含任何范围。
移动右指针right++，范围内的字符只有一个p，继续挪动右指针直到
right=2
，子串为
“pww”出现了重复字符'w'
；
如上图right=2时，出现重复字符，此时右移左指针，右移一次left++，依旧存在重复元素，继续右移left++，直到[l…r]只有一个字符’w’。
这时开始右移右指针right，移动right的前提是[l…r]中不存在重复元素。
如上图，当right=5时再次出现重复元素，移动左指针，字符串为“kew”。此时的right已经到移动到终点，下面一直挪动左指针，直到left抵达终点。
此时left=5，但left并没有结束。还需要移动一次，只有当left=length即left=6时才算遍历结束。
上面就是整个滑动窗口指针移动的过程。
关于如何考虑字符串是否重合，不可能说右指针所指的字符和范围内的每一个字符进行比较查看是否有重复。可以用一个记录频次的数组，来记录0-256字符的频次。遍历的每一个字符都查看它的当前频次，为0则不重复，如果已经遍历过，一定要把频次+1。
因为是求最长子串，所以初始化res为0，判断每一个子串与res的长度取最大值。
class Solution {
public int lengthOfLongestSubstring(String s) {
int l = 0, r = -1; // 滑动窗口[l..r]
int res = 0;
int[] freq = new int[256];
while (l < s.length()) {
// if (freq[s.charAt(r + 1)] == 0 && r + 1 < s.length())非法
// r + 1 < s.length()的判断必须在前面防止越界
if (r + 1 < s.length() && freq[s.charAt(r + 1)] == 0 )
freq[s.charAt(++r)]++;
else
freq[s.charAt(l++)]--;
res = Math.max(res, r - l + 1);
}
return res;
}
// 本地测试
public static void main(String[] args) {
String str = "abcabcbb";
System.out.println(new Solution().lengthOfLongestSubstring(str));
}
}
切记在进行r的边界判断是，要先判断它是否越界再进行+1。即
r + 1 < s.length()的判断必须写在前面
。