详解顺序结构滑动窗口处理算法
🎀个人主页： 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 = 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 set = new HashSet(); int lenMax=0; while(end（3）存在重复元素 II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) public boolean containsNearbyDuplicate(int[] nums, int k) { int numLength = nums.length; Set if(set.contains(nums[end])){ return true; } set.add(nums[end]); while (end - start = k){ set.remove(nums[start]); start++; } } return false; } }
总结
滑动窗口算法是一种用于解决数组或字符串中子序列（子数组或子串）问题的有效技巧。它通过维护一个动态的窗口，不断调整窗口的起始和结束位置，以满足问题的条件。以下是滑动窗口算法的关键特点、优势和应用场景：
- 关键特点：
- 使用两个指针（通常是起始指针和结束指针）表示窗口的边界。
- 通过不断移动窗口的边界，动态调整窗口的大小。
- 用于解决需要求解子序列最优解的问题。
- 优势：
- 高效： 滑动窗口算法通常具有线性时间复杂度，因为每个元素或字符只需被访问一次。
- 空间效率： 使用常数级的额外空间，不需要存储整个子序列的信息，而是通过维护窗口的边界来解决问题。
- 简洁： 算法思路相对简单，易于理解和实现。
- 应用场景：
- 最长子串或子数组： 用于求解最长不含重复字符的子串、最短子数组等问题。
- 满足条件的子串： 用于找到满足特定条件的子串，如包含指定字符、和大于等于某个值的子数组等。
- 窗口内的统计信息： 用于在移动窗口的过程中动态计算窗口内元素的统计信息，如和、平均值等。
- 固定长度的窗口： 用于处理固定长度的窗口，例如计算滑动窗口的平均值。
- 注意事项：
- 确保窗口的起始和结束位置的移动是合理的，避免重复计算和漏算。
- 处理窗口的边界条件，确保不越界。
总体来说，滑动窗口算法是一种高效、简洁的解决子序列问题的方法，在处理字符串和数组等数据结构时广泛应用。
文中有不对的地方欢迎指正、补充。
-
-
