算法每日双题精讲——滑动窗口(长度最小的子数组,无重复字符的最长子串)
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟
别再犹豫了!快来订阅我们的算法每日双题精讲专栏,一起踏上算法学习的精彩之旅吧!💪
目录
💯前言
💯滑动窗口的作用
💯长度最小的子数组
题目描述:
⭐解题思路:
🙋这个解题思路是怎么来的呢?
代码实现(以 C++ 为例):
👀复杂度分析:
💯无重复字符的最长子串
题目描述:
⭐解题思路:
🙋这个解题思路是怎么来的呢?
代码实现(以 C++ 为例):
👀复杂度分析:
💯总结
💯前言
在算法的领域中,滑动窗口算法犹如一把精巧的钥匙,能够高效地开启许多数组和字符串相关问题的求解之门。今日,我们将聚焦于两道经典题目 ——“长度最小的子数组” 和 “无重复字符的最长子串”,深入领略滑动窗口算法的魅力与应用技巧。
✍当面临在给定数据结构中查找满足特定条件的子结构问题时,滑动窗口算法常常能为我们提供清晰且高效的解题思路。
💯滑动窗口的作用
滑动窗口算法借助两个同向指针来界定一个动态的 “窗口”,在数组或字符串上逐步滑动。通过不断调整窗口的大小和位置,实时监控窗口内元素的特性,从而快速定位到符合要求的子序列或子串。这种方法避免了对所有可能子结构的暴力枚举,显著提高了算法效率。
💯长度最小的子数组
题目链接👉【力扣】
题目描述:
给定一个包含 n
个正整数的数组和一个正整数 target
,找出该数组中满足其和 ≥ target
的长度最小的连续子数组,并返回其长度。若不存在符合条件的子数组,则返回 0
。
⭐解题思路:
- 初始化双指针
left
和right
,均指向数组起始位置,sum
用于记录当前窗口内元素之和,初始化为0
,minLength
记录最小子数组长度,初始化为一个较大值(如INT_MAX
)。- 移动
right
指针向右扩展窗口,将新元素累加到sum
中。- 当
sum
≥target
时,尝试移动left
指针向右收缩窗口,同时更新sum
。在此过程中,不断比较当前窗口长度与minLength
,若当前长度更小,则更新minLength
。- 重复步骤 2 和 3,直到
right
指针到达数组末尾。- 最后,若
minLength
仍为初始值,返回0
;否则,返回minLength
。
🙋这个解题思路是怎么来的呢?
我们首先最容易想到解法一:暴力求解
👇现在我们来分析以下数组:
起初我们让left=right=0,此时sum=2,(sum为left到right之间的和)
sum=2 < target,我们让 right++,sum变成了2+3
当right走到这个位置时,sum=2+3+1+2=8>target,我们计算len=right-left ,然后让left++,sum减去第一个left所指的值
sum<target,我们继续让 right++
重复以上步骤,记录最小的len,直到 right<n
代码实现(以 C++ 为例):
class Solution {
public:int minSubArrayLen(int target, vector<int>& 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_set<char>
来记录窗口内出现过的字符。- 移动
right
指针向右扩展窗口,将新字符插入集合中。- 若新插入字符已在集合中,说明出现重复,此时移动
left
指针向右收缩窗口,同时从集合中移除窗口左侧字符,直到窗口内无重复字符。- 在每次移动指针后,更新无重复字符的最长子串长度。
- 重复步骤 2 - 4,直到
right
指针到达字符串末尾。
🙋这个解题思路是怎么来的呢?
我们首先最容易想到解法一:暴力求解
👇现在我们来分析以下字符串:
让left=right=0,创建哈希表
如果right不在hash里面,将right的值存在hash里面,right++
当right所指的值已经在哈希表里了,我们计算len=right-left
接着我们让 left 走到与 right 所指的值的后面 ,即a的后面
重复以上过程,找到最大的len,直到right<n
代码实现(以 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】