img
相信看了这个标题的同学，对这道题以已经非常不陌生了，就是leecode当中的第三题，之所以要单独的写一写主要对我来说，里面涉及到有一个滑动窗口, 散列表， 字符编码等知识点比较重要，也有几个小技巧，这里我也权当记忆巩固了，这道题也曾被Micosoft, Amazon, Bloomberg, Airbnb, Adobe作为经典面试题，包括限流, TCP拥塞都有使用到滑动窗口思想。
题目
给给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1: 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
举例：
img
作为大多数人，找出如图的不相同字符的最大长度，基本上判断3次，ABC长度为3，BCAD长度为4，CADC长度为3，判断到这里直接就可以给出答案了，就是4，因为CADC已经到字符串末尾了，不用再比较了。但是让程序去实现这个功能就要设计一下了。
根据事例提出几个问题：
①在第一轮判定了ABC都不重复，我们怎么实现将BC作为一个整体第二轮就不需要要判断BC是不重复的子串?
②如何选取数据结构？
<font face="黑体">滑动窗口：</font>
顾名思义，滑动窗口通常指可以动态扩容和缩容的一个窗口，如"ABCADC“这个事例，在第二轮我们视BC为一个整体进行扩容，扩容到BCAD。
img
img
如”pwwkew“，在第二轮当PW遇到W，我们进行缩容，直接从下一个W开始。如图所示。通常滑动窗口的实现需要结合散列表来实现来维护一个不重复子串，当获取接下来的字符如果存在在散列表中，指针右移。
img
img
img
散列表：
通常一旦涉及到出现次数，我们可以用散列表，在Java中我们常用的涉及到散列表的容器有HashMap， HashSet, HashTable等等。这里我们可以选用HashSet,其实其它几种都可以实现。
Set<Character> occ = new HashSet<>(); // 创建一个散列表
occ.remove(s.charAt(i - 1)); // 指针右移(移除）
occ.add((s.charAt(rk + 1))); // 指针右移(添加)
!occ.contains(s.charAt(rk + 1)) // 判断接下来的字符是否出现在散列表
参考代码
public static int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<>();
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));
}
if (ans >= n -i) {
break;
}
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;
}
测试用例：
@Test
public void islengthOfLongestSubstring() {
// int i = lengthOfLongestSubstring("abcadc");
int i = lengthOfLongestSubstring("pwwkew");
Assert.assertNotNull(i);
}
拓展
public int lengthOfLongestSubstring1(String s) {
if(s==null||s.equals(""))
return 0;
int []map = new int[256];
for(int i=0;i<256;i++)
map[i]=-1;
int len = 0, cur = 0, pre = -1;
for(int i=0;i<s.length();i++){
int x = s.charAt(i);
pre = Math.max(pre,map[x]); // 记录上次比较出现过得最大值
cur = i - pre; // 指针 - 最大值,当指针右移，i变大，他们的差值就越大;出现相同的值，pre变大
len = Math.max(len,cur);
map[x] = i; // 对出现过的字符赋值为字符串下标
}
return len;
}
我们知道，在计算机中，所有的数据在存储和运算时都要使用二进制数表示，在英语中，用128个符号编码便可以表示所有，其他语言，128个符号是不够的。一些欧洲国家决定，利用字节中闲置的最高位编入新的符号，这些欧洲国家使用的编码体系，可以表示最多256个符号。但是汉字多达10万左右，汉字使用GB2312，理论上可以表示 256 x 256 = 65536 个符号。
在本题中主要只涉及到字符串，完全可以使用一个数组，容量大小是256，初始长度都为-1，出现过的值记录一下，pre比较出现过的值，通过右移指针与pre的差来记录最近一次最大值，len为历史最大值。
热门推荐：
文末福利，最近整理一份面试资料《Java面试通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：GitHub github.com/Tingyu-Notes，更多内容关注我的简书，陆续奉上。
网友评论