【算法题攻略】滑动窗口

文章目录一、习题解析1. 长度最小的子数组详细图解总结了 滑动窗口的思想2. 最大连续 1 的个数 III3. 将 x 减到 0 的最小操作数解题思维正难则反4. 找到字符串中所有字母异位词二、练习题1. 串联所有单词的子串hard2. 最小覆盖子串一、习题解析1. 长度最小的子数组详细图解总结了 滑动窗口的思想题目链接: 209. 长度最小的子数组题目描述找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。示例 1输入target 7, nums [2,3,1,2,4,3]输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2输入target 4, nums [1,4,4]输出1示例 3输入target 11, nums [1,1,1,1,1,1,1,1]输出0提示1 target 1091 nums.length 1051 nums[i] 1041解法一2解法二以 滑动窗口的思想 优化解法一总结滑动窗口的思想代码实现classSolution{public:intminSubArrayLen(inttarget,vectorintnums){intsum0;intlen0;intleft0;intright0;while(rightnums.size())// right越界就跳出循环{// 1. 进窗口sumnums[right];// 2. 判断while(sumtarget){if((right-leftlen)||len0){// 更新结果lenright-left;}// 3. 出窗口sum-nums[left];}}returnlen;}};2. 最大连续 1 的个数 III题目链接: 最大连续 1 的个数 III题目描述给定一个二进制数组 nums 和一个整数 k假设最多可以翻转 k 个 0 则返回执行操作后 数组中连续 1 的最大个数 。示例 1输入nums [1,1,1,0,0,0,1,1,1,1,0]K 2输出6解释[1,1,1,0,0,1,1,1,1,1,1]粗体数字从 0 翻转到 1最长的子数组长度为 6。示例 2输入nums [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]K 3输出10解释[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]粗体数字从 0 翻转到 1最长的子数组长度为 10。提示1 nums.length 10^5nums[i] 不是 0 就是 10 k nums.length代码实现classSolution{public:intlongestOnes(vectorintnums,intk){intleft0,right0;intsum_zero0;intlen0;while(rightnums.size()){// 1. 进窗口if(nums[right]0)sum_zero;// 2. 判断while(sum_zerok){if(right-left-1len)// 更新结果lenright-left-1;// 3. 出窗口if(nums[left]0)sum_zero--;}}if(right-leftlen)lenright-left;returnlen;}};3. 将 x 减到 0 的最小操作数解题思维正难则反题目链接: 1658. 将 x 减到 0 的最小操作数题目描述给你一个整数数组 nums 和一个整数 x 。每一次操作时你应当移除数组 nums 最左边或最右边的元素然后从 x 中减去该元素的值。请注意需要 修改 数组以供接下来的操作使用。如果可以将 x 恰好 减到 0 返回 最小操作数 否则返回 -1 。示例 1输入nums [1,1,4,2,3]x 5输出2解释最佳解决方案是移除后两个元素将 x 减到 0 。示例 2输入nums [5,6,7,8,9]x 4输出-1示例 3输入nums [3,2,20,1,1,3]x 10输出5解释最佳解决方案是移除后三个元素和前两个元素总共 5 次操作将 x 减到 0 。提示1 nums.length 10^51 nums[i] 10^41 x 10^9代码实现classSolution{public:intminOperations(vectorintnums,intx){intsum0;for(autoit:nums){sumit;}if(sumx)return-1;if(sumx)returnnums.size();intleft0,right0;inttargetsum-x;intcount_sum0;intlen0;while(rightnums.size()){// 1. 进窗口count_sumnums[right];// 2. 判断while(count_sumtarget){if(count_sumtargetright-leftlen){// 更新结果lenright-left;}// 3. 出窗口count_sum-nums[left];}}if(len0)return-1;elsereturnnums.size()-len;}};4. 找到字符串中所有字母异位词题目链接: 438. 找到字符串中所有字母异位词题目描述给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1输入s “cbaebabacd”, p “abc”输出[0,6]解释起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。示例 2输入s “abab”, p “ab”输出[0,1,2]解释起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。提示1 s.length, p.length 3 * 10^4s 和 p 仅包含小写字母1解法一2解法二优化解法一 的判断条件代码实现classSolution{public:vectorintfindAnagrams(string s,string p){vectorintvec;if(p.size()s.size())returnvec;inthash_1[26]{0};inthash_2[26]{0};intcount0;// 记录有效字母个数for(autoit:p){hash_1[it-a];}intleft0,right0;while(rights.size()){hash_2[s[right]-a];if(hash_2[s[right]-a]hash_1[s[right]-a])count;if(right-left1p.size()){if(countp.size())vec.push_back(left);hash_2[s[left]-a]--;if(hash_2[s[left]-a]hash_1[s[left]-a])count--;left;}right;}returnvec;}};二、练习题1. 串联所有单词的子串hard题目链接: 30. 串联所有单词的子串题目描述给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。-例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串因为他不是任何 words 排列的连接。返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。示例 1输入s “barfoothefoobarman”, words [“foo”,“bar”]输出[0,9]解释因为 words.length 2 同时 words[i].length 3连接的子字符串的长度必须为 6。子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2输入s “wordgoodgoodgoodbestword”, words [“word”,“good”,“best”,“word”]输出[]解释因为 words.length 4 并且 words[i].length 4所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。示例 3输入s “barfoofoobarthefoobarman”, words [“bar”,“foo”,“the”]输出[6,9,12]解释因为 words.length 3 并且 words[i].length 3所以串联子串的长度必须为 9。子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。提示1 s.length 10^41 words.length 50001 words[i].length 30words[i] 和 s 由小写英文字母组成解题思路与 “找到字符串中所有字母异位词” 的解题思路一致前者是用哈希表计算 各种字母的个数而此题是用 哈希表计算 各种字符串的个数前者是用 count 来计算有效字母的个数而此题是用 count 来计算有效字符串的个数2. 最小覆盖子串题目链接: 76. 最小覆盖子串题目描述给定两个字符串 s 和 t长度分别是 m 和 n返回 s 中的 最短窗口 子串使得该子串包含 t 中的每一个字符包括重复字符。如果没有这样的子串返回空字符串 “”。测试用例保证答案唯一。示例 1输入s “ADOBECODEBANC”, t “ABC”输出“BANC”解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。示例 2输入s “a”, t “a”输出“a”解释整个字符串 s 是最小覆盖子串。示例 3输入s “a”, t “aa”输出“”解释t 中两个字符 ‘a’ 均应包含在 s 的子串中因此没有符合条件的子字符串返回空字符串。提示m s.lengthn t.length1 m, n 105s 和 t 由英文字母组成解题思路参考 “找到字符串中所有字母异位词” 的解法用哈希表计算的 每个字母的个数用 count 来计算有效字母的个数