中级题目可能已经是我的极限了 先看题目吧:
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题目理解上应该没有任何问题,主要就是找出不重复的子串,这里题目很贴心的给出了子序列和子串的区别,子串需要是连续的.
脑子里只有暴力算法,但直觉告诉自己一定会超时.
很没有出息地看了题解,主要是通过滑动窗口来实现,滑动窗口这个名词第一次听说是在计算机网络的课程里面----滑动窗口协议,已经忘得差不多了,应该要去复习一次了.
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i,j)[i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i,j)[i, j)[i,j) 向右滑动 111 个元素，则它将变为 [i+1,j+1)[i+1, j+1)[i+1,j+1)（左闭，右开）。
这个滑动窗口有什么用呢?
我个人的理解是维持一个窗口,不断向右延伸j,倘若右边的第一个未在窗口内的字符与窗口内的字符不重复,则把该字符加入窗口中,窗口的j+1向右延伸,如果该字符重复了,说明找到了以当前i(左端)的最长无重复子串,因此将i从窗口中移除(缩短),i+1进行下一轮的查找.
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
当然,官方题解中又给出了优化方案,是针对当找到重复数字后,仅仅将左端i向右移动1格会导致i+1到j部分的子串又被重复检测,造成浪费.因此使用了hashmap,把当前查找到的无重复最长子串的后一个位置,也就是j+1存储,并且在下一次循环中,把i设置成j+1,跳过那些已经遍历过的元素.
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
理解起来其实不是很容易,而且实在是想不出来这么...新鲜的算法,可能还是练太少了吧
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
