物流网站建设策划书的总结,哪里能做网站,ppt下载免费完整版,学视频剪辑报个班的多少钱#x1f31f;快来参与讨论#x1f4ac;#xff0c;点赞#x1f44d;、收藏⭐、分享#x1f4e4;#xff0c;共创活力社区。 #x1f31f; 别再犹豫了#xff01;快来订阅我们的算法每日双题精讲专栏#xff0c;一起踏上算法学习的精彩之旅吧#xff01;#x1f4aa;… 快来参与讨论点赞、收藏⭐、分享共创活力社区。 别再犹豫了快来订阅我们的算法每日双题精讲专栏一起踏上算法学习的精彩之旅吧 目录
前言
滑动窗口的作用
长度最小的子数组 题目描述
⭐解题思路
这个解题思路是怎么来的呢 代码实现以 C 为例
复杂度分析
无重复字符的最长子串 题目描述
⭐解题思路
这个解题思路是怎么来的呢
代码实现以 C 为例
复杂度分析
总结 前言 在算法的领域中滑动窗口算法犹如一把精巧的钥匙能够高效地开启许多数组和字符串相关问题的求解之门。今日我们将聚焦于两道经典题目 ——“长度最小的子数组” 和 “无重复字符的最长子串”深入领略滑动窗口算法的魅力与应用技巧。 ✍当面临在给定数据结构中查找满足特定条件的子结构问题时滑动窗口算法常常能为我们提供清晰且高效的解题思路。 滑动窗口的作用 滑动窗口算法可有趣啦它用两个同向的指针来定义一个会动的 “窗口” 哦这个窗口就像一个调皮的小精灵在数组或者字符串里跑来跑去呢。通过不停地调整窗口的大小和位置它能时刻知道窗口里面元素的情况这样就能很快找到我们想要的子序列或者子串啦。这种方法可比那种傻傻地把所有可能的子结构都检查一遍的暴力枚举法强多啦它能让算法的效率像火箭一样飞起来呢
滑动窗口是利用单调性用 “同向双指针” 来实现优化的哦。简单来说呢就是指针只向前走不会后退哦。
操作步骤大概是这样滴 先把left和right都设成0然后把元素放进窗口里接着判断一下如果满足条件就缩小窗口如果不满足就扩大窗口最后别忘了更新结果哦。就这样一直重复直到把整个数据结构都遍历完。这样就能巧妙地避开那些没必要的计算啦是不是很聪明呢 长度最小的子数组
题目链接【力扣】
题目描述
给定一个包含 n 个正整数的数组和一个正整数 target找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。若不存在符合条件的子数组则返回 0。 ⭐解题思路 初始化双指针 left 和 right均指向数组起始位置sum 用于记录当前窗口内元素之和初始化为 0minLength 记录最小子数组长度初始化为一个较大值如 INT_MAX。移动 right 指针向右扩展窗口将新元素累加到 sum 中。当 sum ≥ target 时尝试移动 left 指针向右收缩窗口同时更新 sum。在此过程中不断比较当前窗口长度与 minLength若当前长度更小则更新 minLength。重复步骤 2 和 3直到 right 指针到达数组末尾。最后若 minLength 仍为初始值返回 0否则返回 minLength。 这个解题思路是怎么来的呢
我们首先最容易想到解法一暴力求解 现在我们来分析以下数组 起初我们让leftright0此时sum2sum为left到right之间的和 sum2 target,我们让 right,sum变成了23 当right走到这个位置时sum23128target我们计算lenright-left 然后让leftsum减去第一个left所指的值
sumtarget我们继续让 right
重复以上步骤记录最小的len直到 rightn 代码实现以 C 为例 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size(); // 获取数组nums的大小int left 0; // 滑动窗口的左边界指针初始化为0int right 0; // 滑动窗口的右边界指针初始化为0int sum 0; // 用于记录当前滑动窗口内元素的总和int len INT_MAX; // 初始化为INT_MAX用于记录满足条件的最小子数组长度// 开始移动右边界指针right来扩展滑动窗口while (right n) {sum nums[right]; // 将当前右边界指向的元素加入到总和sum中// 当当前滑动窗口内元素总和sum大于等于目标值target时while (sum target) {len std::min(len, right - left 1); // 更新最小子数组长度len取当前窗口长度与之前记录的最小值中的较小值sum - nums[left]; // 将窗口左边界对应的元素从总和sum中减去left; // 左边界指针向右移动一位尝试缩小窗口继续寻找更小的满足条件的子数组}right; // 右边界指针向右移动一位继续扩展窗口}// 如果len仍然是INT_MAX说明没有找到满足条件的子数组返回0否则返回lenreturn len INT_MAX? 0 : len;}
}; 复杂度分析 时间复杂度其中 n 为数组长度。最坏情况下right 指针遍历整个数组一次left 指针最多也遍历整个数组一次。空间复杂度仅需额外常数级别的空间存储指针和变量。 无重复字符的最长子串
题目链接【力扣】
题目描述
给定一个字符串 s找出其中不含有重复字符的最长子串的长度。 ⭐解题思路 初始化 left 和 right 指针指向字符串起始位置使用 unordered_setchar 来记录窗口内出现过的字符。移动 right 指针向右扩展窗口将新字符插入集合中。若新插入字符已在集合中说明出现重复此时移动 left 指针向右收缩窗口同时从集合中移除窗口左侧字符直到窗口内无重复字符。在每次移动指针后更新无重复字符的最长子串长度。重复步骤 2 - 4直到 right 指针到达字符串末尾。 这个解题思路是怎么来的呢 我们首先最容易想到解法一暴力求解 现在我们来分析以下字符串 让leftright0,创建哈希表 如果right不在hash里面将right的值存在hash里面right 当right所指的值已经在哈希表里了我们计算lenright-left 接着我们让 left 走到与 right 所指的值的后面 即a的后面
重复以上过程找到最大的len直到rightn 代码实现以 C 为例 class Solution {
public:// 函数用于计算给定字符串s中的最长无重复字符子串的长度int lengthOfLongestSubstring(string s) {// 创建一个大小为128的数组用于记录每个字符出现的次数初始化为0// 假设字符串中的字符ASCII码值范围在0 - 127之间int hash[127 1] {0}; int left 0; // 滑动窗口的左边界指针初始化为0int right 0; // 滑动窗口的右边界指针初始化为0int ret 0; // 用于记录最长无重复字符子串的长度初始化为0int n s.size(); // 获取字符串s的长度// 开始移动右边界指针right来扩展滑动窗口while (right n) {// 将右边界指针right指向的字符在hash数组中的计数加1hash[s[right]];// 当右边界指针right指向的字符出现次数大于1时即出现重复字符while (hash[s[right]] 1) {// 将左边界指针left指向的字符在hash数组中的计数减1并将左边界指针left向右移动一位hash[s[left]]--;}// 更新最长无重复字符子串的长度ret取当前窗口长度right - left 1与之前记录的ret中的较大值ret std::max(ret, right - left 1);right; // 右边界指针right向右移动一位继续扩展窗口}return ret; // 返回最长无重复字符子串的长度}
}; 复杂度分析 时间复杂度:外层循环遍历字符串内层循环虽可能多次执行但左、右边界指针总共移动次数最多为 2n 次整体时间复杂度为 n 是字符串长度。空间复杂度:仅用了固定大小的数组 hash 及几个固定占用空间的变量空间复杂度为 。 总结 ✍通过对这两道题目的深入剖析我们深切体会到滑动窗口算法在处理数组和字符串问题时的高效性与灵活性。它通过巧妙维护窗口状态避免了冗余计算快速定位目标子结构。希望大家在后续算法学习中熟练掌握此算法轻松应对类似挑战。 我将持续在算法领域深耕细作为大家带来更多精彩的算法知识讲解与问题解析。欢迎大家关注我
【A Charmer】
