个人主页： https://zhangxiaoshu.blog.csdn.net 欢迎大家：关注+点赞+评论+收藏⭐️，如有错误敬请指正! 未来很长，值得我们全力奔赴更美好的生活！
前言
在数据结构和算法方面的面试中，数组和字符串的相关问题往往是一个重要的考察点。面试官通常会测试面试者在处理这些基础数据结构时的熟练程度，因为这直接关系到解决实际问题的能力。在数组和字符串的考察中，双指针和滑动窗口以及排序算法、字符串的处理API成为关键技巧，本文主要对滑动窗口进行简单介绍。
文章目录
前言1. 序2. 滑动窗口原理3. 应用场景（1）长度最小的子数组（2）无重复字符的最长子串（3）存在重复元素 II
总结
1. 序
双指针和滑动窗口是在处理数组和字符串问题时常用的技巧。双指针通常用于解决数组中的一些查找或判断问题，通过设置两个指针在数组上移动，实现对数组的遍历和比较。滑动窗口则常用于解决字符串中的子串或子数组问题，通过维护一个可变大小的窗口在字符串上滑动，从而实现对子串或子数组的探测。
排序算法在面试中同样是一个重要的考察点，因为它与数组相关，对数据的整理和查找提供了基础。熟练掌握常见的排序算法，如快速排序、归并排序等，有助于在解决各种问题时更高效地处理数组。此外，对于字符串的处理API也是面试中需要掌握的知识。熟悉字符串的各种操作，如查找子串、替换字符、反转字符串等，能够帮助面试者更灵活地处理字符串相关的问题。
本文主要是对滑动窗口这种常用技巧进行简要介绍，帮助读者在面对数组和字符串相关问题时能够更加从容应对。深入理解这些技巧，并在实际问题中灵活运用，将有助于提高面试者在数据结构和算法面试中的表现。
2. 滑动窗口原理
滑动窗口法是一种在处理数组或字符串的子序列（子数组或子串）问题时常用的技巧。它通过维护一个动态的窗口来解决问题，窗口的起始和结束位置会根据问题的要求进行滑动。这种方法通常用于求解最长子串、最短子数组等问题。
基本思路：
初始化窗口的起始位置和结束位置。通常使用两个指针，比如 start 和 end，表示窗口的左右边界。 通过移动窗口的结束位置，扩大窗口。根据问题的要求，可以通过增加 end 指针的位置来扩展窗口。 通过移动窗口的起始位置，缩小窗口。当窗口包含的元素满足某个条件时，可以通过增加 start 指针的位置来缩小窗口。 重复以上步骤直到满足问题的条件。 在每一步中，都可以根据问题的要求更新窗口的状态，并在遍历完整个数组或字符串后得到问题的解。
滑动窗口法的优势在于它能够在线性时间内解决很多子序列问题，而无需使用额外的空间。这使得它在处理大规模数据时表现良好。
3. 应用场景
（1）长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
具体思路如下：
初始化变量 ans 为整数的最大值 Integer.MAX_VALUE，start 和 end 分别表示当前子数组的起始和结束位置，sum 表示当前子数组的和。 使用 while 循环遍历数组 nums，其中 end 指针负责扩大窗口，start 指针负责缩小窗口。 在循环中，先将当前元素加到 sum 中，然后检查是否满足 sum >= target 的条件。如果满足，说明当前窗口的子数组和大于等于目标值，此时进入内部的 while 循环。 在内部的 while 循环中，不断缩小窗口，即通过减去 nums[start] 的值来减小 sum。同时，更新 ans 为当前窗口的长度 end - start + 1 和 ans 之前值的较小值。这样，通过不断缩小窗口，可以找到满足条件的最小子数组。 重复上述过程，直到 end 指针遍历完整个数组。 返回最终结果 ans，如果 ans 仍然为 Integer.MAX_VALUE，说明没有找到满足条件的子数组，返回 0；否则，返回找到的最小子数组的长度。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while(end < nums.length){
sum += nums[end];
while(sum >= target){
sum-=nums[start];
ans = Math.min(ans,end-start+1);
start++;
}
end++;
}
return ans== Integer.MAX_VALUE ? 0 : ans;
}
}
（2）无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
具体思路如下：
初始化指针和数据结构： 使用 start 和 end 两个指针来表示当前子串的起始和结束位置，使用 HashSet 来存储当前子串中出现的字符。lenMax 用于记录最长不含重复字符的子串长度。 滑动窗口： 通过不断移动 end 指针，扩大窗口。当遇到重复字符时，开始缩小窗口。 处理重复字符：如果当前字符是新字符，将其添加到 set 中，然后更新 lenMax 为当前子串的长度（end - start + 1）的最大值。如果当前字符已经在 set 中，表示有重复字符，需要将 start 指针右移，并将对应的字符从 set 中移除，直到子串中不再包含重复字符。 遍历完整个字符串： 通过不断移动 end 指针和更新 lenMax，直到 end 指针遍历完整个字符串。 返回结果： 返回最终的 lenMax，即最长不含重复字符的子串的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
int start=0;
int end=0;
HashSet
int lenMax=0;
while(end < s.length()){
if(set.add(s.charAt(end))){
lenMax=Math.max(lenMax,end-start+1);
end++;
}else{
set.remove(s.charAt(start));
start++;
}
}
return lenMax;
}
}
（3）存在重复元素 II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。 输入：nums = [1,2,3,1], k = 3 输出：true
初始化数据结构： 使用一个 LinkedHashSet 来存储当前窗口中的元素，保持插入顺序。 遍历数组： 使用两个指针 start 和 end 遍历数组，其中 end 指针负责扩大窗口，start 指针负责缩小窗口。 判断重复元素： 在每一步中，首先检查当前窗口中是否包含数组中的元素 nums[end]。如果存在，表示存在重复元素，直接返回 true。 保持窗口大小： 在窗口大小达到 k 之后，通过缩小窗口，即移除 set 中的元素 nums[start]，并将 start 指针右移。 遍历完整个数组： 重复上述步骤，直到 end 指针遍历完整个数组。 返回结果： 如果在遍历过程中未找到重复元素，返回 false。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
int numLength = nums.length;
Set
for(int start = 0, end = 0; end < numLength; end++){
if(set.contains(nums[end])){
return true;
}
set.add(nums[end]);
while (end - start >= k){
set.remove(nums[start]);
start++;
}
}
return false;
}
}
总结
滑动窗口算法是一种用于解决数组或字符串中子序列（子数组或子串）问题的有效技巧。它通过维护一个动态的窗口，不断调整窗口的起始和结束位置，以满足问题的条件。以下是滑动窗口算法的关键特点、优势和应用场景：
关键特点：
使用两个指针（通常是起始指针和结束指针）表示窗口的边界。通过不断移动窗口的边界，动态调整窗口的大小。用于解决需要求解子序列最优解的问题。
优势：
高效： 滑动窗口算法通常具有线性时间复杂度，因为每个元素或字符只需被访问一次。空间效率： 使用常数级的额外空间，不需要存储整个子序列的信息，而是通过维护窗口的边界来解决问题。简洁： 算法思路相对简单，易于理解和实现。
应用场景：
最长子串或子数组： 用于求解最长不含重复字符的子串、最短子数组等问题。满足条件的子串： 用于找到满足特定条件的子串，如包含指定字符、和大于等于某个值的子数组等。窗口内的统计信息： 用于在移动窗口的过程中动态计算窗口内元素的统计信息，如和、平均值等。固定长度的窗口： 用于处理固定长度的窗口，例如计算滑动窗口的平均值。
注意事项：
确保窗口的起始和结束位置的移动是合理的，避免重复计算和漏算。处理窗口的边界条件，确保不越界。
总体来说，滑动窗口算法是一种高效、简洁的解决子序列问题的方法，在处理字符串和数组等数据结构时广泛应用。
文中有不对的地方欢迎指正、补充。
文章来源
发表评论