广州制作网站公司简介,网站开发公司 商业计划书,全网品牌营销,百度指数关键词搜索趋势#x1f380;个人主页#xff1a; https://zhangxiaoshu.blog.csdn.net #x1f4e2;欢迎大家#xff1a;关注#x1f50d;点赞#x1f44d;评论#x1f4dd;收藏⭐️#xff0c;如有错误敬请指正! #x1f495;未来很长#xff0c;值得我们全力奔赴更美好的生活个人主页 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, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。 输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。 具体思路如下 初始化变量 ans 为整数的最大值 Integer.MAX_VALUEstart 和 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-start1);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 start0;int end0;HashSetCharacter set new HashSetCharacter();int lenMax0;while(end s.length()){ if(set.add(s.charAt(end))){lenMaxMath.max(lenMax,end-start1);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;SetInteger 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;}
}总结
滑动窗口算法是一种用于解决数组或字符串中子序列子数组或子串问题的有效技巧。它通过维护一个动态的窗口不断调整窗口的起始和结束位置以满足问题的条件。以下是滑动窗口算法的关键特点、优势和应用场景
关键特点
使用两个指针通常是起始指针和结束指针表示窗口的边界。通过不断移动窗口的边界动态调整窗口的大小。用于解决需要求解子序列最优解的问题。
优势
高效 滑动窗口算法通常具有线性时间复杂度因为每个元素或字符只需被访问一次。空间效率 使用常数级的额外空间不需要存储整个子序列的信息而是通过维护窗口的边界来解决问题。简洁 算法思路相对简单易于理解和实现。
应用场景
最长子串或子数组 用于求解最长不含重复字符的子串、最短子数组等问题。满足条件的子串 用于找到满足特定条件的子串如包含指定字符、和大于等于某个值的子数组等。窗口内的统计信息 用于在移动窗口的过程中动态计算窗口内元素的统计信息如和、平均值等。固定长度的窗口 用于处理固定长度的窗口例如计算滑动窗口的平均值。
注意事项
确保窗口的起始和结束位置的移动是合理的避免重复计算和漏算。处理窗口的边界条件确保不越界。
总体来说滑动窗口算法是一种高效、简洁的解决子序列问题的方法在处理字符串和数组等数据结构时广泛应用。
文中有不对的地方欢迎指正、补充。
