- 好文 滑动窗口详解 - 力扣
一、无重复字符的最长子串
解法一
i、j：两个下标构造成一个窗口
每次找到的不重复子串长度：j - i
取最大值
使用indexOf方法，对窗口内的字符串进行重复判断
class Solution {
public int lengthOfLongestSubstring(String s) {
int rscount = 0;
int i = 0;
int j = i;
if(s.length() > 0) {
while(j < s.length()) {
//从第 i + 1 个字符位置开始往后继续查找，包含当前位置
if(s.indexOf(s.charAt(j), i) == j) {//找到自己的索引，则无重复
j++;
} else {//找到较为前面的索引，说明早已出现，出现重复
rscount = rscount > j - i ? rscount : j - i;
i++;
j = i;
}
}
rscount = rscount > j - i ? rscount : j - i;
}
return rscount;
}
}
-
String 的 indexOf方法：
indexOf() 方法有以下四种形式：
- public int indexOf(int ch): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
- public int indexOf(int ch, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
- int indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
- int indexOf(String str, int fromIndex): 返回从 fromIndex 位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
解法二
i、j：构成窗口、字串
循环判断窗口中的符号是否已在map中保存
存在重复：i 等于重复的字符的下一位的索引、得到map的size、再清空map，新窗口出现
不重复字串长度取MAX(map的size)
class Solution {
public int lengthOfLongestSubstring(String s) {
int rscount = 0;
int i = 0;
int j = i;
Map<Character, Integer> map = new HashMap<Character, Integer>();
if(s.length() > 0) {
while(j < s.length()) {
if(map.get(s.charAt(j)) == null) {//在map中找不到该键
map.put(s.charAt(j), j);
j++;
} else {//map中存在该键
rscount = rscount > map.size() ? rscount : map.size();
i = map.get(s.charAt(j)) + 1;
j = i;
map.clear();
}
}
rscount = rscount > map.size() ? rscount : map.size();
}
return rscount;
}
}
解法三
解法二改进：
根据map查询得知，右指针的符号存在重复
不清空map，而是删除左指针的元素，左指针自增 也就是，map中的保存的窗口字符删除了左指针的符号 继续循环 直到在map中删除了右指针的重复字符 右指针才可自增、给map添加符号map保存字符内容和数量
联想：用队列替换map？效果会更好？
出队、入队很快，查找可能差点每次删除前，取map、rscount最大值
class Solution {
public int lengthOfLongestSubstring(String s) {
int rscount = 0;
//一左一右
int i = 0;
int j = i;
Map<Character, Integer> map = new HashMap<Character, Integer>();
if(s.length() > 0) {
while(j < s.length()) {
if(map.get(s.charAt(j)) == null) {//在map中找不到该键
map.put(s.charAt(j), j);
j++;
} else {//map中存在该键
rscount = rscount > map.size() ? rscount : map.size();
map.remove(s.charAt(i));
++i;
}
}
rscount = rscount > map.size() ? rscount : map.size();
}
return rscount;
}
}
解法一优化
删除 重复时 ： j = i
右指针 j 只在不重复情况下自增，出现重复则调整左指针 i 自增，直到无重复
j = i 的坏处：使窗口大小变为0，判断的重复次数剧增
class Solution {
public int lengthOfLongestSubstring(String s) {
int rscount = 0;
int i = 0;
int j = i;
if(s.length() > 0) {
while(j < s.length()) {
//从第 i + 1 个字符位置开始往后继续查找，包含当前位置
if(s.indexOf(s.charAt(j), i) == j) {//找到自己的索引，则无重复
j++;
} else {//找到较为前面的索引，说明早已出现，出现重复
rscount = rscount > j - i ? rscount : j - i;
i++;
}
}
rscount = rscount > j - i ? rscount : j - i;
}
return rscount;
}
}
解法二优化
map不清空
右指针 j 只在不重复情况下自增，出现重复则调整左指针 i 自增，直到无重复
- j = i 的坏处：使窗口大小变为0，判断的重复次数剧增
不重复条件：map.get(s.charAt(j)) == null || map.get(s.charAt(j)
- 首先是不存在map中
- 要是存在了，就取其索引，并判断是否在左右指针的区间内：小于 i 则是不在窗口内‘
存在重复就更新 MAX（rscount，j - i）
class Solution {
public int lengthOfLongestSubstring(String s) {
int rscount = 0;
int i = 0;
int j = i;
Map<Character, Integer> map = new HashMap<Character, Integer>();
if(s.length() > 0) {
while(j < s.length()) {
if(map.get(s.charAt(j)) == null || map.get(s.charAt(j)) < i) {//在map中找不到该键
map.put(s.charAt(j), j);
j++;
} else {//map中存在该键
rscount = rscount > j - i ? rscount : j - i;
i = map.get(s.charAt(j)) + 1;
}
}
rscount = rscount > j - i ? rscount : j - i;
}
return rscount;
}
}
结果
二、字符串的排列
s1的排列之一是s2的 子串 ：s1.length <= s2.length 成立
- 维护两个元素数组 arr1、arr2
- 分别统计s1、s2的前 s1.length 个字符
- 用于判断子串排列是否存在
- 只要符号、数量一样即可
- 符号是数组小标（索引）
- 数量就是对应下标的值
子串长度固定：s1.length
- 那么在s2的滑动窗口（检测子串的窗口），大小固定为s1.length
移动窗口在 s2 的 位置寻找是否有合适的子串
循环条件：
- 总共需移动指针 s2.length() - count 次
- 且 s2 的 [index，index + count) 范围内组成的字串 不是 s1 的排列之一
- 根据arr1、arr2数组是否相等
- 维护arr2数组：将index索引的字符数量减一、index+count字符数量加一，index自增
- 结果判断
- 如果检测完所有子串（循环检测少了最后一个），则 index 等于s2.length() - count
- 最后返回检测arr1 和 arr2 数组是否相同即可
- 因为后几位已被计入arr2数组中
- 如果是checkArray(arr1, arr2)返回真而结束的循环
- 说明是arr1、arr2相等，有符合的子串，返回true
class Solution {
public boolean checkInclusion(String s1, String s2) {
if(s1.length() <= s2.length()) {
int[] arr1 = new int[26];
int[] arr2 = new int[26];
for(int i = 0; i < s1.length(); i++) {
arr1[s1.charAt(i) - 'a'] += 1;
arr2[s2.charAt(i) - 'a'] += 1;
}
int count = s1.length();
int index = 0;
while(index < s2.length() - count && !checkArray(arr1, arr2)) {
if(s2.charAt(index) != s2.charAt(index + count)) {
arr2[s2.charAt(index) - 'a'] -= 1;
arr2[s2.charAt(index + count) - 'a'] += 1;
}
++index;
}
if(index == s2.length() - count) {
return checkArray(arr1, arr2);
}
return true;
}
return false;
}
private boolean checkArray(int[] arr1, int[] arr2) {
for(int i = 0; i < arr1.length; i++) {
if(arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
}
