![[LC优选算法#2] 滑动窗口 | 长度最小的子数组 | 无重复字符的最长子串 | 最大连续1的个数](images/news1.jpg)
1. 算法思想滑动窗口的本质是维护一个满足条件的连续子数组/子串通过移动左右边界来“滑动”这个窗口从而找到最优解。滑动窗口是更加严格的双指针算法大致思路都是用两个不回退的指针维护窗口。而且滑动窗口仅支持元素为正数的情况不适用于负数或0出窗口的时机无法确定。基本步骤进窗口 - 判断条件 - 出窗口 - 更新结果更新结果的时机因题而异2. 经典例题2.1 ⻓度最⼩的⼦数组⻓度最⼩的⼦数组解题思路暴力解法O(N^2)从数组中的每个元素开始向后枚举找出满足条件的最小长度。显然暴力解法中存在很多重复的计算。例如下图如果按照暴力枚举的方式统计当2枚举结束后需要从3开始重新计算长度但3之后的12都是没必要重新计数的。根据这一点我们可以试着维护一个“窗口”来解决重复统计的耗时问题。滑动窗口O(N)这个窗口满足内部所有元素之和小于target的条件。如果窗口内元素之和大于等于target则更新结果然后在逐个排除左边元素的同时继续判断是否符合条件并继续更新结果如果元素之和不满足条件则加入新元素。时间复杂度由于维护窗口的left和right指针都是不回退的最坏情况是两者分别遍历一次数组因此总共耗时 2*N时间复杂度为O(N)。classSolution{public:intminSubArrayLen(inttarget,vectorintnums){intnnums.size();intlenINT_MAX;intsum0;for(intleft0,right0;rightn;right){sumnums[right];while(sumtarget){lenmin(len,right-left1);sum-nums[left];left;}}returnlenINT_MAX?0:len;}};2.2 ⽆重复字符的最⻓⼦串⽆重复字符的最⻓⼦串解题思路暴力解法哈希表O(N^2)从数组中的每个元素开始向后枚举找出满足条件的最大长度。用哈希表统计出字符出现的频次来判断什么时候子串出现了重复元素。显然研究对象依旧是一段连续的区间以下图为例在枚举完d后没有必要以e、a为起点重新向后枚举因为重复元素a仍然在橙色区间中枚举的长度只会更短。因此我们可以通过向右缩小窗口直至满足条件绿色区间然后继续让新元素进窗口。2.滑动窗口哈希表O(N)右端元素进⼊窗⼝的时候哈希表统计这个字符的频次如果这个字符出现的频次超过1说明窗⼝内有重复元素那么就从左侧开始划出窗⼝直到这个元素的频次变为 1 然后再更新结果如果小于1说明当前窗⼝没有重复元素可以直接更新结果。时间复杂度由于维护窗口的left和right指针都是不回退的最坏情况是两者分别遍历一次数组因此总共耗时 2*N时间复杂度为O(N)。classSolution{public:intlengthOfLongestSubstring(string s){intleft0;intright0;intns.size();intmaxlen0;vectorinthash(128,0);//128个字符用数组模拟哈希表while(rightn){hash[s[right]];while(hash[s[right]]2)//加1在前判断在后则为2{hash[s[left]]--;}maxlenmax(maxlen,right-left1);right;}returnmaxlen;}};2.3 最⼤连续 1 的个数 III最⼤连续 1 的个数 III解题思路可以翻转最多 k 个 0 转化为找一个包含 k 个 0的最长区间。暴力解法O(N^2)以每个元素为起点依次向后找最长的子数组。题目包含连续区间考虑用滑动窗口思想解决滑动窗口O(N)窗口内部存放有k个0的连续子串以子串中0的个数为判断条件维护窗口超出k个0则停止更新left指针左移不够k个0则right指针右移更新窗口。classSolution{public:intlongestOnes(vectorintnums,intk){intleft0;intright0;intzerocnt0;intlen0;intnnums.size();while(rightn){if(nums[right]0){zerocnt;}while(zerocntk){if(nums[left]0){zero--;}}lenmax(len,right-left1);right;}returnlen;}};// 本期内容就到这里如果对你有帮助请三连支持我是青云我们下期见^_~
[LC优选算法#2] 滑动窗口 | 长度最小的子数组 | 无重复字符的最长子串 | 最大连续1的个数
1. 算法思想滑动窗口的本质是维护一个满足条件的连续子数组/子串通过移动左右边界来“滑动”这个窗口从而找到最优解。滑动窗口是更加严格的双指针算法大致思路都是用两个不回退的指针维护窗口。而且滑动窗口仅支持元素为正数的情况不适用于负数或0出窗口的时机无法确定。基本步骤进窗口 - 判断条件 - 出窗口 - 更新结果更新结果的时机因题而异2. 经典例题2.1 ⻓度最⼩的⼦数组⻓度最⼩的⼦数组解题思路暴力解法O(N^2)从数组中的每个元素开始向后枚举找出满足条件的最小长度。显然暴力解法中存在很多重复的计算。例如下图如果按照暴力枚举的方式统计当2枚举结束后需要从3开始重新计算长度但3之后的12都是没必要重新计数的。根据这一点我们可以试着维护一个“窗口”来解决重复统计的耗时问题。滑动窗口O(N)这个窗口满足内部所有元素之和小于target的条件。如果窗口内元素之和大于等于target则更新结果然后在逐个排除左边元素的同时继续判断是否符合条件并继续更新结果如果元素之和不满足条件则加入新元素。时间复杂度由于维护窗口的left和right指针都是不回退的最坏情况是两者分别遍历一次数组因此总共耗时 2*N时间复杂度为O(N)。classSolution{public:intminSubArrayLen(inttarget,vectorintnums){intnnums.size();intlenINT_MAX;intsum0;for(intleft0,right0;rightn;right){sumnums[right];while(sumtarget){lenmin(len,right-left1);sum-nums[left];left;}}returnlenINT_MAX?0:len;}};2.2 ⽆重复字符的最⻓⼦串⽆重复字符的最⻓⼦串解题思路暴力解法哈希表O(N^2)从数组中的每个元素开始向后枚举找出满足条件的最大长度。用哈希表统计出字符出现的频次来判断什么时候子串出现了重复元素。显然研究对象依旧是一段连续的区间以下图为例在枚举完d后没有必要以e、a为起点重新向后枚举因为重复元素a仍然在橙色区间中枚举的长度只会更短。因此我们可以通过向右缩小窗口直至满足条件绿色区间然后继续让新元素进窗口。2.滑动窗口哈希表O(N)右端元素进⼊窗⼝的时候哈希表统计这个字符的频次如果这个字符出现的频次超过1说明窗⼝内有重复元素那么就从左侧开始划出窗⼝直到这个元素的频次变为 1 然后再更新结果如果小于1说明当前窗⼝没有重复元素可以直接更新结果。时间复杂度由于维护窗口的left和right指针都是不回退的最坏情况是两者分别遍历一次数组因此总共耗时 2*N时间复杂度为O(N)。classSolution{public:intlengthOfLongestSubstring(string s){intleft0;intright0;intns.size();intmaxlen0;vectorinthash(128,0);//128个字符用数组模拟哈希表while(rightn){hash[s[right]];while(hash[s[right]]2)//加1在前判断在后则为2{hash[s[left]]--;}maxlenmax(maxlen,right-left1);right;}returnmaxlen;}};2.3 最⼤连续 1 的个数 III最⼤连续 1 的个数 III解题思路可以翻转最多 k 个 0 转化为找一个包含 k 个 0的最长区间。暴力解法O(N^2)以每个元素为起点依次向后找最长的子数组。题目包含连续区间考虑用滑动窗口思想解决滑动窗口O(N)窗口内部存放有k个0的连续子串以子串中0的个数为判断条件维护窗口超出k个0则停止更新left指针左移不够k个0则right指针右移更新窗口。classSolution{public:intlongestOnes(vectorintnums,intk){intleft0;intright0;intzerocnt0;intlen0;intnnums.size();while(rightn){if(nums[right]0){zerocnt;}while(zerocntk){if(nums[left]0){zero--;}}lenmax(len,right-left1);right;}returnlen;}};// 本期内容就到这里如果对你有帮助请三连支持我是青云我们下期见^_~
