目录引言209. 长度最小的子数组题目分析逻辑梳理代码实现复杂度分析3. 无重复字符的最长子串题目分析逻辑梳理代码实现复杂度分析1004. 最大连续1的个数 III题目分析逻辑梳理代码实现复杂度分析结语引言滑动窗口是处理数组/字符串子区间问题的经典技巧。本文将通过三道 LeetCode 高频题由浅入深地讲解双指针滑动窗口的核心思想与应用技巧。题目核心技巧长度最小的子数组正数单调性 → 双指针收缩求最值无重复字符的最长子串哈希判重 → 动态维护合法窗口最大连续 1 的个数 III状态标记 → 转化约束条件209. 长度最小的子数组题目分析给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。逻辑梳理由于数组元素均为正数子数组的和具有单调性——窗口扩大时和增加缩小时和减少。这一性质使得双指针滑动窗口成为天然的选择维护窗口[l, r)其中l为起始位置r为结束位置的下一个位置左闭右开ret记录当前窗口内元素之和若ret target说明窗口还需扩大r右移并将新元素加入和若ret target说明当前窗口满足条件更新最小长度随后尝试收缩窗口l右移并将离开窗口的元素从和中扣除当r到达数组末尾后当前窗口可能仍满足条件需在外层继续收缩并更新答案代码实现class Solution { public: int minSubArrayLen(int target, vectorint nums) { int len 0x3f3f3f3f; int l 0,r 1; long long ret nums[0]; while(rnums.size()) { if(rettarget) { retnums[r]; } else { len min(r-l,len); ret-nums[l]; } } while(rettarget) { len min(r-l,len); ret-nums[l]; } return len0x3f3f3f3f?0:len; } };复杂度分析时间复杂度O(N)每个元素最多被l和r各访问一次空间复杂度O(1)仅使用常数个额外变量3. 无重复字符的最长子串题目分析给定一个字符串s找出其中不含有重复字符的最长子串的长度。逻辑梳理本题与上一题思路一脉相承核心差异在于窗口的合法性条件由和 ≥ target变为无重复字符。借助哈希表或数组记录字符出现次数即可 O(1)判断重复st[200]作为字符频次数组ASCII 范围足够覆盖常见字符l指向当前无重复子串的起始位置遍历右端点i若s[i]已存在于窗口中则不断右移l直至s[i]不再重复每次将s[i]纳入窗口后更新最大长度代码实现class Solution { public: int lengthOfLongestSubstring(string s) { int st[200]{}; int l 0,ans 0; for(int i 0; is.size();i) { while(st[s[i]]) { st[s[l]]--; } st[s[i]]; ans max(ans,i-l1); } return ans; } };复杂度分析时间复杂度O(N)左右指针均单向移动每个字符最多被访问两次空间复杂度O(1)固定大小的频次数组与输入规模无关1004. 最大连续1的个数 III题目分析给定一个由若干 0 和 1 组成的数组nums以及整数k最多可以将k个 0 翻转为 1返回最长的连续 1 的子数组长度。逻辑梳理本题是滑动窗口的变体应用将最多翻转 k 个 0转化为窗口内 0 的个数不超过 k。为了优雅地处理翻转状态的回退采用一个技巧——将翻转过的 0 标记为 2l初始化为-1窗口起始前一个位置r为窗口结束位置遇到nums[r] 1直接扩展窗口更新答案遇到nums[r] 0且还有剩余翻转次数k将其翻转为 2k--更新答案遇到nums[r] 0但无剩余次数右移l直至遇到第一个被翻转的 2将其恢复为 0k的等价操作随后将当前r位置的 0 翻转为 2。此过程中窗口长度不变仅需继续右移r代码实现class Solution { public: int longestOnes(vectorint nums, int k) { int ans 0; int l -1,r 0,tmp k; while(rnums.size()) { if(nums[r]0) { if(k) { nums[r]2; k--; ans max(ans,r-l); } else { while(k0lr) { l; if(nums[l]2) { nums[r] 2; break; } } } } else if(nums[r]1) { ans max(ans,r-l); } r; } return ans; } };复杂度分析时间复杂度O(N)l和r均最多遍历数组一次空间复杂度O(1)原地修改数组未使用额外数据结构结语掌握滑动窗口的关键在于识别问题的单调性明确定义窗口的合法性条件并保证双指针的单向移动。当遇到子数组/子串最值问题时不妨优先考虑这一利器。希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。
每日算法精讲 Day 5 | leetcode 209. 长度最小的子数组、leetcode 3. 无重复字符的最长子串、leetcode 1004. 最大连续1的个数 III
目录引言209. 长度最小的子数组题目分析逻辑梳理代码实现复杂度分析3. 无重复字符的最长子串题目分析逻辑梳理代码实现复杂度分析1004. 最大连续1的个数 III题目分析逻辑梳理代码实现复杂度分析结语引言滑动窗口是处理数组/字符串子区间问题的经典技巧。本文将通过三道 LeetCode 高频题由浅入深地讲解双指针滑动窗口的核心思想与应用技巧。题目核心技巧长度最小的子数组正数单调性 → 双指针收缩求最值无重复字符的最长子串哈希判重 → 动态维护合法窗口最大连续 1 的个数 III状态标记 → 转化约束条件209. 长度最小的子数组题目分析给定一个含有 n 个正整数的数组和一个正整数 target找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0。逻辑梳理由于数组元素均为正数子数组的和具有单调性——窗口扩大时和增加缩小时和减少。这一性质使得双指针滑动窗口成为天然的选择维护窗口[l, r)其中l为起始位置r为结束位置的下一个位置左闭右开ret记录当前窗口内元素之和若ret target说明窗口还需扩大r右移并将新元素加入和若ret target说明当前窗口满足条件更新最小长度随后尝试收缩窗口l右移并将离开窗口的元素从和中扣除当r到达数组末尾后当前窗口可能仍满足条件需在外层继续收缩并更新答案代码实现class Solution { public: int minSubArrayLen(int target, vectorint nums) { int len 0x3f3f3f3f; int l 0,r 1; long long ret nums[0]; while(rnums.size()) { if(rettarget) { retnums[r]; } else { len min(r-l,len); ret-nums[l]; } } while(rettarget) { len min(r-l,len); ret-nums[l]; } return len0x3f3f3f3f?0:len; } };复杂度分析时间复杂度O(N)每个元素最多被l和r各访问一次空间复杂度O(1)仅使用常数个额外变量3. 无重复字符的最长子串题目分析给定一个字符串s找出其中不含有重复字符的最长子串的长度。逻辑梳理本题与上一题思路一脉相承核心差异在于窗口的合法性条件由和 ≥ target变为无重复字符。借助哈希表或数组记录字符出现次数即可 O(1)判断重复st[200]作为字符频次数组ASCII 范围足够覆盖常见字符l指向当前无重复子串的起始位置遍历右端点i若s[i]已存在于窗口中则不断右移l直至s[i]不再重复每次将s[i]纳入窗口后更新最大长度代码实现class Solution { public: int lengthOfLongestSubstring(string s) { int st[200]{}; int l 0,ans 0; for(int i 0; is.size();i) { while(st[s[i]]) { st[s[l]]--; } st[s[i]]; ans max(ans,i-l1); } return ans; } };复杂度分析时间复杂度O(N)左右指针均单向移动每个字符最多被访问两次空间复杂度O(1)固定大小的频次数组与输入规模无关1004. 最大连续1的个数 III题目分析给定一个由若干 0 和 1 组成的数组nums以及整数k最多可以将k个 0 翻转为 1返回最长的连续 1 的子数组长度。逻辑梳理本题是滑动窗口的变体应用将最多翻转 k 个 0转化为窗口内 0 的个数不超过 k。为了优雅地处理翻转状态的回退采用一个技巧——将翻转过的 0 标记为 2l初始化为-1窗口起始前一个位置r为窗口结束位置遇到nums[r] 1直接扩展窗口更新答案遇到nums[r] 0且还有剩余翻转次数k将其翻转为 2k--更新答案遇到nums[r] 0但无剩余次数右移l直至遇到第一个被翻转的 2将其恢复为 0k的等价操作随后将当前r位置的 0 翻转为 2。此过程中窗口长度不变仅需继续右移r代码实现class Solution { public: int longestOnes(vectorint nums, int k) { int ans 0; int l -1,r 0,tmp k; while(rnums.size()) { if(nums[r]0) { if(k) { nums[r]2; k--; ans max(ans,r-l); } else { while(k0lr) { l; if(nums[l]2) { nums[r] 2; break; } } } } else if(nums[r]1) { ans max(ans,r-l); } r; } return ans; } };复杂度分析时间复杂度O(N)l和r均最多遍历数组一次空间复杂度O(1)原地修改数组未使用额外数据结构结语掌握滑动窗口的关键在于识别问题的单调性明确定义窗口的合法性条件并保证双指针的单向移动。当遇到子数组/子串最值问题时不妨优先考虑这一利器。希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。