3.无重复字符的最长子串
题目：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:
输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。 示例 4:
输入: s = "" 输出: 0
提示：
0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Java版答案(博主答案)
class Solution {
public int lengthOfLongestSubstring(String s) {
final int length = s.length();
if (2 > length)
return length;
Set<Character> charSet = new HashSet<>();
int max = 0;
for (int i = 0, index = 0, tempMax = 0; i < length; i++)
if (charSet.add(s.charAt(i))) {
if (++tempMax > max)
max = tempMax;
} else {
int j = index;
for (; s.charAt(j) != s.charAt(i); j++)
charSet.remove(s.charAt(j));
tempMax -= (j - index);
index = j + 1;
}
return max;
}
}
解析
我的答案是很朴素的，模拟循环遍历，将当前最大值与历史最大值比较、更新。遇到重复的，将重复值之前的删除，寻找超过最大值的可能。 时间和空间复杂度都是o(n)。
Java版答案(官方答案)
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
解析
官方答案是抽象后的答案，先将问题抽象化，然后将对抽象的问题求解。
抽象出滑动窗口这个概念后，采用左指针右移一位，右指针尽可能右移，Math.max(a,b)其实就是与历史最大相比，更新最大值。
Java版答案（网友答案）
class Solution {
public int lengthOfLongestSubstring(String s) {
// 记录字符上一次出现的位置
int[] last = new int[128];
for(int i = 0; i < 128; i++) {
last[i] = -1;
}
int n = s.length();
int res = 0;
int start = 0; // 窗口开始位置
for(int i = 0; i < n; i++) {
int index = s.charAt(i);
start = Math.max(start, last[index] + 1);
res = Math.max(res, i - start + 1);
last[index] = i;
}
return res;
}
}
解析
网友的这个答案就厉害了。
有点像是桶这个概念，先把字符串集（ASCII 码）初始化为-1，用来记录字符上次出现的位置。 在遍历的时候，每个字符集的桶都会保存这个字符在字符串的下标（最新下标）。
之后就是遍历字符串，start 是左指针，如果当前字符串没有重复（默认桶的值是-1），-1+ 1= 0（ start = Math.max(start, last[index] + 1);）,左指针就还是上一个字符串重复的左指针，否则，左指针就变成了字符重复（重复字符的第一个字符）的左指针 + 1。
而长度也比较有意思，长度就是历史最大长度与当前长度相比的最大值（当前最大长度是右指针 - 左指针 + 1）。
使用两个max函数，将滑动窗口这个算法由之前的求连续性字符子串的最大长度变成了求两次最大值。
因为窗口函数总是从左向右滑动。 左指针和右指针都是慢慢变大。
我的答案是对解题过程的模拟抽象。
官方答案是对这个解题过程进行抽象，然后对抽象问题求解。
官方答案到我的答案，区别不大。但是思维不同。
网友的答案是在滑块窗口的基础上，通过几步转换，将复杂的问题改为了求最大值的问题。（桶思想、左右指针永远是单向思想）。