目录1.长度最小的子数组2.无重读字符的最长字串3. 最大连续1的个数4.将x减小到0的最小操作数5.水果成篮6.找到字符串中所有字母异位词7.串联所有单词的子集8.最小覆盖字串1.长度最小的子数组. - 力扣LeetCode对于从同一端往另一端移动的双指针我们可以采用滑动窗口的策略解决。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int ret INT_MAX; int left 0; int sum 0; int right 0; for(left 0, right 0; right nums.size(); right) { sum nums[right];//进窗口 while(sum target)//判断 { ret min(ret,right - left 1); sum - nums[left]; left; } } return ret INT_MAX ? 0 : ret; return ret; } };如例子 2 3 1 2 4 3我们让left和right从下标为0处出发让right不断右移一直让left到right这段的子数组之和大于等于目标数。当left到right这段的子数组之和大于等于目标数时再向后移动时子数组的长度会更长因此我们通过将left右移判断能否减去一些较小的数使范围内的子数组长度减小但是仍然大于目标数。若可以将每次的结果和ret比较比如 1 2 3 4 50 目标数为40.直到子数组小于目标数了在让right右移。但也有可能整个数组加起来都达不到目标数的大小我们可以事先遍历判断也可以判断ret是否被赋值过来进行返回2.无重读字符的最长字串. - 力扣LeetCodeclass Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] {0}; int size s.size(); int left 0; int right 0; int ret 0; for(right; right size; right) { hash[s[right]]; while(hash[s[right]] 1) { hash[s[left]]--; left; } ret max(ret,right-left 1); } return ret; } };3. 最大连续1的个数. - 力扣LeetCodeclass Solution { public: int longestOnes(vectorint nums, int k) { int ret 0; int sum 0; int size nums.size(); int left 0; int right 0; for(right; right size; right) { if(nums[right] 0)sum; while(sum k) { if(nums[left] 0)sum--; left; } ret max(ret,right - left 1); } return ret; } };4.将x减小到0的最小操作数. - 力扣LeetCodeclass Solution { public: int minOperations(vectorint nums, int x) { int target 0; int size nums.size(); for(int i 0 ;i size; i) { target nums[i]; } target - x; if(target 0)return -1;//如果数组总和还没有x大那就不能把x减到0直接返回-1 int left 0; int right 0; int count 0; int ret -1; for(;right size; right) { count nums[right]; while(count target) { count - nums[left]; left; } if(count target)(ret max(ret,right-left 1)); } return ret -1 ? ret : size - ret; } };这个题目直接正面做不好做我们可以转化为子数组中和为x的最长长度这样即可用滑动窗口做题5.水果成篮. - 力扣LeetCodeclass Solution { public: int totalFruit(vectorint fruits) { int n fruits.size(); vectorintarr(n,0); int left 0; int right 0; int count 0; int ret 0; for(;right n;right) { arr[fruits[right]]; if( arr[fruits[right]] 1)count; while(count 2) { arr[fruits[left]]--; if( arr[fruits[left]] 0)count--; left; } if(count 1)ret max(ret,right-left1); } return ret; } };这里我们引进一个计数器 用于判断是否需要出窗口。仅有新水果第一次入窗口count才会增加。当count 2 时出窗口。6.找到字符串中所有字母异位词. - 力扣LeetCode首先我们还是先存一个哈希表用一个数组简单表示就可以了。hash1表示目标字符串中的字符情况hash2表示left到right字符串中的字符情况#define N 128 class Solution { public: bool judge(int* hash1,int* hash2) { for(int i 0; i N; i) { if(hash1[i] ! hash2[i])return false; } return true; } vectorint findAnagrams(string s, string p) { int size p.size(); int hash1[N] {0}; for(int i 0; i size; i) { hash1[p[i]]; } int hash2[N] {0}; vectorint ret; int left 0; int right 0; for(right;right s.size(); right) { hash2[s[right]]; while(right- left 1 size)//这里其其实用if更合适因为窗口的长度固定达到长度之 //后right移动一次left移动一次最多只会超过一个 { hash2[s[left]]--; left; } if(judge(hash1,hash2))ret.push_back(left); } return ret; } };第一个代码的思路和前面一样先入窗口判断长度不能超过目标字符串长度进行出窗口然后再判断是否符合条件。我们这里写一个判断函数来判断hashi1和hash2一样不一样。class Solution { public: vectorint findAnagrams(string s, string p) { int size p.size(); int hash1[128] {0}; for(int i 0; i size; i) { hash1[p[i]]; } int hash2[128] {0}; int count 0; vectorint ret; int left 0; int right 0; for(right;right s.size(); right) { hash2[s[right]]; if(hash2[s[right]] hash1[s[right]])count; if(right-left1 size) { hash2[s[left]]--; if(hash2[s[left]] hash1[s[left]])count--; left; } if(count size)ret.push_back(left); } return ret; } };第二个代码时间复杂度要低很多这里我们维护一个count来计算有效字符的个数。我们进行入窗口操作时我们先入窗口然后判断当hash2中对应位置 hash1中对应位置时该字符有效也就是我们还需要这个字符比如我们需要两个a当入窗口后a的个数为1或者a的个数为2我们都是需要的此时count 1。当字符串里面的字符超过我们需要的值时对该字符的计数增加但是有效字符数不增加这时候我们就可能遇到right-left1 目标字符串长度 这时候我们不断出窗口直到符合要求这时候我们也同时判断有效字符是否减小。7.串联所有单词的子集. - 力扣LeetCodeclass Solution { public: vectorint findSubstring(string s, vectorstring words) { int len words[0].size(); int size words.size(); unordered_mapstring,int hash1;//储存words的hash1 for(auto ch:words) { hash1[ch]; } vectorint ret; for(int i 0; i len; i) { int count 0; int left i; int right i; unordered_mapstring,int hash2;//储存遍历的hash2 for(;right s.size(); right len) { //入窗口substr(right,rightlen) string in s.substr(right,len); hash2[in]; if(hash1[in] hash2[in] hash1[in])count; while(right - left 1 len * size) { string out s.substr(left,len); hash2[out]--; if(hash1[out] hash2[out] hash1[out])count--; left len; } if(count size)ret.push_back(left); } } return ret; } };由于words中所有单词都是等长的因此我们可以将一个字符串看为一组以字符串的长度len为窗口一次滑动的距离即单位长度 。然后定义一个哈希表思路同68.最小覆盖字串. - 力扣LeetCodeclass Solution { public: string minWindow(string s, string t) { int hash1[128]{0}; int hash2[128] {0}; int kinds 0; int count 0; int minlen INT_MAX; int begin -1; for(auto ch:t) { hash1[ch]; if(hash1[ch] 1)kinds; } for(int left 0,right 0,count 0;right s.size();right) { int in s[right]; hash2[in]; if(hash2[in] hash1[in])count; while(count kinds) { if(right - left 1 minlen) { minlen right-left1; begin left; } int out s[left]; hash2[out]--; if(hash2[out] hash1[out])count--; left; } } if(begin -1)return ; else return s.substr(begin,minlen); } };定义两个哈希表我们这里采用kinds变量来储存遍历时需要进行判断的种类数。利用count计数判断当hash1与hash2中同位置的值相等count。即有一个字符满足了题目要求。这题要求我们取最小长度所以我们right一直向右移动直到left到right包含所有的目标字符然后出窗口查看是否有更优解。