当前位置：首页 > news >正文

详解顺序结构滑动窗口处理算法

news 文章来源：https://blog.csdn.net/qq_46009046/article/details/135888823 2024/11/15 12:11:29

🎀个人主页： 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<Character> set = new HashSet<Character>();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<Integer> set = new LinkedHashSet<>();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;}
}

总结

滑动窗口算法是一种用于解决数组或字符串中子序列（子数组或子串）问题的有效技巧。它通过维护一个动态的窗口，不断调整窗口的起始和结束位置，以满足问题的条件。以下是滑动窗口算法的关键特点、优势和应用场景：

关键特点：

使用两个指针（通常是起始指针和结束指针）表示窗口的边界。
通过不断移动窗口的边界，动态调整窗口的大小。
用于解决需要求解子序列最优解的问题。

优势：

高效：滑动窗口算法通常具有线性时间复杂度，因为每个元素或字符只需被访问一次。
空间效率：使用常数级的额外空间，不需要存储整个子序列的信息，而是通过维护窗口的边界来解决问题。
简洁：算法思路相对简单，易于理解和实现。

应用场景：

最长子串或子数组：用于求解最长不含重复字符的子串、最短子数组等问题。
满足条件的子串：用于找到满足特定条件的子串，如包含指定字符、和大于等于某个值的子数组等。
窗口内的统计信息：用于在移动窗口的过程中动态计算窗口内元素的统计信息，如和、平均值等。
固定长度的窗口：用于处理固定长度的窗口，例如计算滑动窗口的平均值。

注意事项：

确保窗口的起始和结束位置的移动是合理的，避免重复计算和漏算。
处理窗口的边界条件，确保不越界。

总体来说，滑动窗口算法是一种高效、简洁的解决子序列问题的方法，在处理字符串和数组等数据结构时广泛应用。

文中有不对的地方欢迎指正、补充。

前言