文章目录
- 前言
- 最长字串专场
- 无重复字符的最长字串
- 至多包含两个不同字串的最长子串
- 至多包含K个不同字串的最长子串
- 长度最小的子数组
- 盛水最多的容器
- 寻找字串异位词(排序)
- 字符串的排序
- 找到字符串中所有字母异位
- 总结
前言
提示：所有的话语都颇为类似，而沉默则千差万别。 --卢梭
趁热打铁，我们继续来研究一些高频、热门的滑动窗口问题。
最长字串专场
先看最高频的推荐题目⭐⭐⭐⭐：
3. 无重复字符的最长子串 - 力扣（LeetCode）
滑动窗口—至多包含两个不同字符的最长子串（leetcode 159）_珠穆拉玛峰的博客-CSDN博客
LeetCode算法日记：340.至多包含K个不同字符的最长子串_算法 至多-CSDN博客
看这题目，我们要怎么处理呢？这种造题是不是自己拿手的，顺着这个思路是不是可以造出很多题目来，总结出一些方法，解滑动窗口的模板呢？
无重复字符的最长字串
参考题目地址：3. 无重复字符的最长子串 - 力扣（LeetCode）
要找到最长的子串，必然要知道无重复字符串的首部和尾部，然后再从中确定最长的那个，因此至少需要两个指针才可以，这也是滑动窗口思想。即使用滑动窗口，深入分析会发现，具体处理来由很多方式。这里介绍一种经典的使用Map的思考。
我们这里定义一个K—V形式的map，key表示的是当前正在访问的字符串，value是器下标索引值。我们每访问一个新元素，都将其下标更新成对应的索引值。
如果已经出现过，就和上图的做法一致，abcabc,当第二次出现a的时候，我们就更新left成为第一个b的所在位置，此时惊奇的事情发生了，left要移动的位置恰好就是map.get(‘a’)+1= 1,我们将‘a’用序列来表示，放在一起就是map.get(s.charAt(i)) + 1。其他情况可以类似考虑，参考上图见解。
当然这里有一种特殊的情况，例如abba，我们再次访问b时，left = map.get(‘b’) + 1 = 2。然后继续访问第二个a，这时 left = map.get(‘a’) + 1 = 1,也就是left要后推的节奏，显然就不对了。所以这里要调整逻辑，保留最大值。
这样就可以了
left = Math.max(left,map.get(s.charAt(i)) + 1);
完整代码如下：
/**
* 最长无重复字串
* @param s
* @return
*/
public static int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0){
return 0;
}
Map<Character,Integer> map = new HashMap<>();
int max = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
if (map.containsKey(s.charAt(right))){
// 确保left一直向前走 不回头
left = Math.max(left,map.get(s.charAt(right)) + 1);
}
map.put(s.charAt(right),right);
max = Math.max(max,right - left + 1);
}
return max;
}
除了上述方法，不用Hash存储索引，也是可以用滑动窗口的思想来解决的，感兴趣的是试一试。
至多包含两个不同字串的最长子串
根据上题目的变种，试想以下，这里如果求包含两个不同字串的最长子串呢。
你需要考虑两个问题：
- 怎么判断是两个
- 什么删除元素
如果还使用上述方法是否行的通，left的值应该怎么求舍？
要判断只有两个元素，当然还是Hash好用一些，每一个时刻，判断HashMap中不得超过3个元素。这里就要解决下一个问题，怎么移除了。
还是采用key-value的含义，这次将字符串里的字符都当做键，在窗口中的最右边的字符位置作为值。我们在看下伪代码是删除的逻辑：
del_index = Collections.min(hashMap.values());
left = del_index + 1;
还是看图更直接一些：
我们可以充分利用Map来解决这个问题：
/**
* 至少包含两个字符的最长子串
* @param s
* @return
*/
public static int lengthOfLongestSubstringTwoDistinct(String s) {
if (s.length() < 3){
return s.length();
}
int left = 0;
int right = 0;
HashMap<Character,Integer> map = new HashMap<>();
int maxLen = 2;
while(left < s.length()){
if (map.size() < 3){
map.put(s.charAt(right),right++);
}
// 如果大于3就靠考虑了
if (map.size() == 3){
// 删除最左侧的位置
int del_idx = Collections.min(map.values());
map.remove(s.charAt(del_idx));
// 更新窗口的位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
至多包含K个不同字串的最长子串
这更改2的位置就可以了，正如上个题目一样：
只要将判断HashMap大小为2改成k就可以了，超过2就是k+ 1，实现不就很简单的事情。
/**
* 至多包含k个字符的最长子串
*
* @param s
* @param k
* @return
*/
public static int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s.length() < k + 1) {
return s.length();
}
int left = 0, right = 0;
HashMap<Character, Integer> hashmap = new HashMap<>();
int maxLen = k;
while (right < s.length()) {
if (hashmap.size() < k + 1) {
hashmap.put(s.charAt(right), right++);
}
// 如果大小达到了k个
if (hashmap.size() == k + 1) {
//
int del_idx = Collections.min(hashmap.values());
hashmap.remove(s.charAt(del_idx));
// 窗口left的新位置
left = del_idx + 1;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
长度最小的子数组
参考题目介绍：209. 长度最小的子数组 - 力扣（LeetCode）
本题目可以使用双指针来解决，可以视为队列法。基本思路是先让元素不断入队，当入队元素和等于target时就记录以下此时队列的容量，如果队列元素之和大于target则开始出队，知道小于target则再入队。
当然如果等于target的情况，则记录以下此时队列的大小，之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
/**
* 长度最小的子数组
* @param target 目标值
* @param nums 数组
* @return 返回大小
*/
public static int minSubArrayLen(int target, int[] nums) {
// 初始化变量
int left = 0, right = 0,sum = 0,min = Integer.MAX_VALUE;
while(right < nums.length){
sum += nums[right++];
while(sum >= target){
min = Math.min(min,right - left);
sum -= nums[left++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
盛水最多的容器
参考地址：11. 盛最多水的容器 - 力扣（LeetCode）
这个题目看似很复杂，但是换个思路很简单的，假设两个指针i，j。指向的水槽板高度分别为h[i],h[j]，此时状态下水槽面积为s(i，j)。由于可容纳水的高度有两个板中的腐短板决定的，因此可以得出面积公式：
s(i，j) = min(h[i],h[j])*(j - i)
那么我们就要考虑以下问题：
每个状态，不论是长板还是短板向中间收缩一格，都会导致水槽边宽度-1变短：
- 若向内移动短板，水槽得短板min(h[i],h[j])可能变大，因此下一个水槽得面积可能会增加
- 若向内移动长板，水槽得短板min(h[i],h[j])不变或者变小，因此下一个水槽得面积一定是变小的
因此，这里初始化双指针分别位于水槽左右两端，循环每轮移动向内移动一格，并更新面积最大值，知道两个指针相遇时跳出；即可获得最大面积。
/**
* 盛最多水的容器
* @param height the height of the array
* @return
*/
public static int maxArea(int[] height) {
int i = 0, j = height.length,res = 0;
while(i < j){
// 那最小向中间移动
res = height[i] < height[j] ?
Math.max(res,(j - i)* height[i++]):
Math.max(res,(j - i)* height[j++]);
}
return res;
}
寻找字串异位词(排序)
如果两个字符串仅仅时字母出现的位置不一样，则称两者互相为对方的一个排列，也常称为异位词。
这里推荐两个题目⭐⭐⭐⭐：
567. 字符串的排列 - 力扣（LeetCode）
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
字符串的排序
参考题目地址：567. 字符串的排列 - 力扣（LeetCode）
本题最简单的方式就是用s1做窗口，依次比较得出结果，但是这样的效率太低，我们看看有没有更好更优的办法。
所谓异位词要抓住两点：
- 字母类型一样
- 出现个数相同
因此，我们可以创建一个为26的数组，每个位置对应a-z的个数，为了方便操作，索引做了调整，
index = s1.charAt(i) - 'a';
这个是字符串常用的技巧。
此时窗口一直向前移动就行了。
charArray[s2.charAt(right) - 'a']++
而left向右移动就执行
int left = right - sLen1；
charArray2[s2.charAt(left) - 'a']--;
完整代码是下面的：
/**
* 字符串的排列
* @param s1
* @param s2
* @return
*/
public static boolean checkInclusion(String s1, String s2) {
// 参数检验
int len1 = s1.length(),len2 = s2.length();
if (len1 > len2){
return false;
}
int[] chars1 = new int[26];
int[] chars2 = new int[26];
// 先读len1
for (int i = 0; i < len1; i++){
chars1[s1.charAt(i) - 'a']++;
chars2[s1.charAt(i) - 'a']++;
}
if (Arrays.equals(chars1, chars2)){
return true;
}
// 注意维护窗口变化
for (int right = len1; right < len2; right++){
chars2[s2.charAt(right) - 'a']++;
int left = right - len1;
chars2[s2.charAt(left) - 'a']--;
if (Arrays.equals(chars1, chars2)){
return true;
}
}
return false;
}
上面只是判断有没有，那么如果让你确定右几个呢？有或者如果存在的话，将异位词的开始位置和结束位置输出出来怎么样？那就看看下一题吧
找到字符串中所有字母异位
参考题目介绍：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
思路可以说是一摸一样，简单改下代码就可以了，唯一不同的是，采用List存放，出现异位词的，记录以下开始位置，那么可以直接将其加入到list中。
开下完整的代码：
/**
* 找到字符串中所有字母异位词
* @param s1
* @param s2
* @return
*/
public static List<Integer> findAnagrams(String s1, String s2) {
// 参数检验
int len1 = s1.length(),len2 = s2.length();
if (len1 > len2){
return new ArrayList<Integer>();
}
int[] chars1 = new int[26];
int[] chars2 = new int[26];
// 先读len1
for (int i = 0; i < len1; i++){
chars1[s1.charAt(i) - 'a']++;
chars2[s1.charAt(i) - 'a']++;
}
ArrayList<Integer> res = new ArrayList<>();
if (Arrays.equals(chars1, chars2)){
res.add(0);
}
// 注意维护窗口变化
for (int left = 0; left < len1 - len2; left++ ){
chars2[s1.charAt(left) - 'a']--;
int right = left + len1;
chars2[s1.charAt(right) - 'a']++;
if (Arrays.equals(chars1, chars2)){
// 拿到最最左位置
res.add(left + 1);
}
}
return res;
}
总结
提示：滑动窗口问题；双指针问题；字符串变种；HashMap的特殊存储；模板套路
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~
也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。
![buuctf_练[羊城杯2020]easyphp](https://img-blog.csdnimg.cn/img_convert/4e502050faa2b63867786d283ff7735a.png)