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 由英文字母、数字、符号和空格组成
Related Topics 哈希表 字符串 滑动窗口
思路：滑动窗口，窗口的定义类似于双指针，left和right，两个指针之间的区域就是窗口。
1、先让right往前走，知道不符合题目条件
2、然后让left往前走，直到如何条件
3、记录结果，重复1、2步骤，直到right到末尾
import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
int left = 0, right = 0;
// 转换为字节数组
char[] charArray = s.toCharArray();
// 通过set判断是否存在重复字符
HashSet<Character> set = new HashSet<>();
while (right <= charArray.length-1) {
// 让right往前走，碰到相同字符时停下来
if (!set.contains(charArray[right])) {
set.add(charArray[right]);
right++;
// 记录结果,为什么放在右指针处，因为有可能全部不重复，左指针都不需要移动
ans = Math.max(ans, right - left);
} else {
// 如果right走不动了，则让left往前走
set.remove(charArray[left]);
left++;
}
}
return ans;
}
}
也可以直接用String中的方法：
import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
int left = 0, right = 0;
// 通过set判断是否存在重复字符
HashSet<Character> set = new HashSet<>();
while (right <= s.length()-1) {
// 让right往前走，碰到相同字符时停下来
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
// 记录结果,为什么放在右指针处，因为有可能全部不重复，左指针都不需要移动
ans = Math.max(ans, right - left);
} else {
// 如果right走不动了，则让left往前走
set.remove(s.charAt(left));
left++;
}
}
return ans;
}
}
567. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false
提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
Related Topics 哈希表 双指针 字符串 滑动窗口
👍 443 👎 0
思路：因为s1排列是s2的子串，所以滑动窗口的大小只要保持和s1一致。
第一版， 解答错误，没有考虑可能会出现字母重复的情况
如：
“hello”
“ooolleoooleh”
import java.util.HashSet;
class Solution {
public boolean checkInclusion(String s1, String s2) {
int left = 0, right = s1.length() - 1;
// 初始化s1的字符set集合
HashSet set = new HashSet<>();
for (int i = 0; i < s1.length(); i++) {
set.add(s1.charAt(i));
}
// 循环结束条件
while (right <= s2.length() - 1) {
// left -> right之间的元素是否都在set中
int i;
for (i = left; i <= right; i++) {
if (!set.contains(s2.charAt(i))) {
// 第i个字符不在s1中，滑动窗口直接移动到i+1位置
left = i + 1;
right = i + s1.length();
break;
}
// 如果最后一个都符合，返回true
if (i == right) {
return true;
}
}
}
return false;
}
}
那就用map记录每个元素的个数，试试
class Solution567 {
public boolean checkInclusion(String s1, String s2) {
int left = 0, right = s1.length() - 1;
// 初始化s1的字符set集合
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s1.length(); i++) {
map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
}
// 循环结束条件
Map<Character, Integer> temp = new HashMap<>();
l:while (right <= s2.length() - 1) {
temp.clear();
// left -> right之间的元素是否都在map中,且个数相同
int i;
for (i = left; i <= right; i++) {
// 不包含直接跳过，简直
if (!map.containsKey(s2.charAt(i))) {
// 第i个字符不在s1中，滑动窗口直接移动到i+1位置
left = i + 1;
right = i + s1.length();
break;
} else {
// 记录一下个数
temp.put(s2.charAt(i), temp.getOrDefault(s2.charAt(i), 0) + 1);
}
// 如果最后一个都符合，且字符个数都相同，返回true
if (i == right) {
for (Map.Entry entry : map.entrySet()) {
if (!entry.getValue().equals(temp.getOrDefault(entry.getKey(), 0))) {
left++;
right++;
continue l;
}
}
return true;
}
}
}
return false;
}
}
嗯，虽然通过了，但结果非常惨烈，同时还调试了很久，执行时间超过了5%的用户
原因是我们忽略了一些题目的条件， “s1 和 s2 仅包含小写字母”,即字符出现的类型是固定的。可以将map转化为数组，ascii码作为数组下标。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < n; ++i) {
++cnt1[s1.charAt(i) - 'a'];
++cnt2[s2.charAt(i) - 'a'];
}
if (Arrays.equals(cnt1, cnt2)) {
return true;
}
for (int i = n; i < m; ++i) {
++cnt2[s2.charAt(i) - 'a'];
--cnt2[s2.charAt(i - n) - 'a'];
if (Arrays.equals(cnt1, cnt2)) {
return true;
}
}
return false;
}
}
另外滑动窗口每次只移动一个位置，而每次需要比较整个数组，比较浪费性能，
可以将数组比较优化为 右边进入的字符与左边出去的字符的ascii码差值。
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < n; ++i) {
--cnt[s1.charAt(i) - 'a'];
++cnt[s2.charAt(i) - 'a'];
}
int diff = 0;
for (int c : cnt) {
if (c != 0) {
++diff;
}
}
if (diff == 0) {
return true;
}
for (int i = n; i < m; ++i) {
int x = s2.charAt(i) - 'a', y = s2.charAt(i - n) - 'a';
if (x == y) {
continue;
}
if (cnt[x] == 0) {
++diff;
}
++cnt[x];
if (cnt[x] == 0) {
--diff;
}
if (cnt[y] == 0) {
++diff;
}
--cnt[y];
if (cnt[y] == 0) {
--diff;
}
if (diff == 0) {
return true;
}
}
return false;
}
}
![LSM 优化系列（四） -- Rocksdb和Lethe 对Delete问题的优化[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)