双指针法的特化 具体体现在指针的同向移动维护的进出窗口 其模板就是r的在循环后的必定与l的陆续弹出和更新结果专题二滑动窗口此类型关键在于 思路的优化迭代在保证r的尽量不回退的前提下与l的陆续弹出。辅助哈希表解决不定的计数问题(像滑动窗口中的是否出窗口完全)。虽然十分不提倡模板的解题使用但模板恰恰反应了解决此类问题的核心本质第一步定义r与l维护区间for后r。第二步更新结果的位置选取 (l的陆续弹出勿跳跃前进)。 //但此陆续弹出不一定指单次循环仅弹出一个。关键在于哈希表的灵活应用。第三步返回的最后结果的特殊情况判断。1.两数和大于值的最小长度给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回0。以r与l维护区间以弹出和入窗口。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int len INT_MAX, sum 0; for(int l 0,r 0;r nums.size();r) { sum nums[r]; while(sum target) { //更新结果 len r - l 1 len? r - l 1:len; sum - nums[l]; } } if(len INT_MAX) return 0; return len; } };2.无重复字符串的最小长度给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。注意 bca 和 cab 也是正确答案。1.思路滑动窗口哈希表简化r的回溯过程 l的跳跃前进r遇到重复固定 l前进至掠过重复元素期间哈希表计数--3.将x减到0的最小操作数给你一个整数数组nums和一个整数x。每一次操作时你应当移除数组nums最左边或最右边的元素然后从x中减去该元素的值。请注意需要修改数组以供接下来的操作使用。如果可以将x恰好减到0返回最小操作数否则返回-1。利用正难则反的编程思想。将原问题转换为求数组中间连续区域的最大长度len后以size()减去len即可。4.水果成篮你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组fruits表示其中fruits[i]是第i棵树上的水果种类。你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果你只有两个篮子并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从每棵树包括开始采摘的树上恰好摘一个水果。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。给你一个整数数组fruits返回你可以收集的水果的最大数目。简言之找一最长区域使得区域内的数据的种数为2/1。为什么使用哈希表 不可以使用三/四指针 因为难以保证[left]数据弹出的完全性。left的单次弹出与哈希表关联。5.找到字符串子串中所有异位串给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。输入:s abab, p ab输出:[0,1,2]解释:起始索引等于 0 的子串是 ab, 它是 ab 的异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的异位词。利用滑动窗口维护区间 哈希表记录 zero记录滑动次数哈希表、zero记载完全滑动。6.串联所有单词的字串hard在了解了思路之后写不出来的原因1.未深入理解算法本质 模板套用未完全套用2.缺失标记量 原有标记量难以实现模板逻辑3.优化不足(指某个逻辑判断这么做会增大代码逻辑复杂度)4.打草严格依据rlen进行单次的l弹出逻辑给定一个字符串s和一个字符串数组words。words中所有字符串长度相同。s中的串联子串是指一个包含words中所有字符串以任意顺序排列连接起来的子串。例如如果words [ab,cd,ef] 那么abcdefabefcdcdabefcdefabefabcd 和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] 也是可以的。class Solution { public: vectorint findSubstring(string s, vectorstring words) { mapstring, int m2; vectorint ret; for(auto e: words) { m2[e]; } int len words[0].size(); for(int i 0;i len ;i) { mapstring, int m1; //原串纳入 // for(int l i, r i;r s.size()-(len*words.size()); r len) for(int l i, r i,zero 0;r s.size(); r len) { //进窗口 m1[s.substr(r, len)]; if(m1[s.substr(r, len)] m2[s.substr(r, len)])//符合条件进入zero zero; //出窗口 同时维护zero的值 if(r - l 1 len*words.size()) { //zero更新-- 哈希退出(--) l变动 //有效字符的推出 if(m1[s.substr(l, len)] m2[s.substr(l, len)]) zero--; m1[s.substr(l, len)]--; // zero--;//代表有效字符啊 llen; } if(zero words.size()) //长度符合 ret.push_back(l); } } return ret; } };7.最小覆盖子串(hard)需要逻辑优化策略给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。示例 1输入s ADOBECODEBANC, t ABC输出BANC解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。