算法2--滑动窗口

滑动窗口

滑动窗口的本质就是同向双指针，而且两个指针都不回退，条件满足就可以让右指针右移使元素进入窗口，否则右移左指针使一些元素退出滑动窗口直至条件满足，由于左右指针都是只向右移动不回退，故其时间复杂度为O(n)，适用于数组等可以下标随机访问的场景。

经典例题

长度最小的子数组

题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的子数组[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int left=0;
        int right=0;
        vector<int> sums;
        int ans=INT_MAX;
        while(right<nums.size())    
        {
            int tmp=sums.size()?sums.back():0;
            sums.push_back(tmp+nums[right++]);
            if(sums.back()>=target)
            {
                int l=left;
                int r=sums.size()-1;
                while(l<=r)
                {
                    if(ans>sums.size())
                    {
                        ans=sums.size();
                    }
                    int mid=(l+r)/2;
                    if(sums.back()-sums[mid]>=target)
                    {
                        left=mid+1;
                        if(ans>right-left)
                        {
                            ans=right-left;
                        }
                        l=mid+1;
                        if(l>=r||sums.back()-sums[l]<target)
                        {
                            break;
                        }
                    }
                    else 
                    {
                        r=mid-1;
                        if(r>=0&&(sums.back()-sums[r]>=target)&&(ans>right-r))
                        {
                            ans=right-r-1;
                        }
                    }
                }
            }
        }

        if(INT_MAX==ans)
        {
            return 0;
        }
        return ans;
    }
};

class Solution
{
public:
	 int minSubArrayLen(int target, vector<int>& nums) 
	 {
		 int n = nums.size(), sum = 0, len = INT_MAX;
		 for(int left = 0, right = 0; right < n; right++)
		 {
			 sum += nums[right]; // 进窗⼝
			 while(sum >= target) // 判断
			 {
				 len = min(len, right - left + 1); // 更新结果
				 sum -= nums[left++]; // 出窗⼝
			 }
		  }
		 return len == INT_MAX ? 0 : len;
	 }
};

无重复字符的最长子串

题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int len=0;
        int curLen=0;
        int left=0;
        int right=0;
        vector<int> counts(256,0);
        while(right<s.size())
        {
            if(1==counts[s[right]])
            {
                curLen=right-left;
                if(len<curLen)
                {
                    len=curLen;
                }
                counts[s[left++]]=0;
            }
            else
            {
                counts[s[right++]]=1;
            }
        }

        curLen=right-left;
        if(len<curLen)
        {
            len=curLen;
        }

        return len;
    }
};

class Solution
{
public:
	 int lengthOfLongestSubstring(string s) 
	 {
		 int hash[128] = { 0 }; // 使⽤数组来模拟哈希表
		 int left = 0, right = 0, n = s.size();
		 int ret = 0;
		 while(right < n)
		 {
			 hash[s[right]]++; // 进⼊窗⼝
			 while(hash[s[right]] > 1) // 判断
			 	hash[s[left++]]--; // 出窗⼝
			 ret = max(ret, right - left + 1); // 更新结果
			 right++; // 让下⼀个元素进⼊窗⼝
		 }
		 return ret;
	 }
};

最大连续1的个数 III

题目描述：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int len=0;
        int curLen=0;
        int left=0;
        int right=0;
        while(right<nums.size())
        {
            if(0==nums[right])
            {
                if(0==k)
                {
                    curLen=right-left;
                    if(len<curLen)
                    {
                        len=curLen;
                    }
                    while(1==nums[left++]);
                    if(left<right)
                    {
                        ++k;
                    }
                    else
                    {
                        right++;
                    }
                }
                else
                {
                    --k;
                    ++right;
                }
            }
            else
            {
                ++right;
            }
        }
        curLen=right-left;
        if(len<curLen)
        {
            len=curLen;
        }

        return len;
    }
};

class Solution
{
public:
	 int longestOnes(vector<int>& nums, int k) 
	 {
		 int ret = 0;
		 for(int left = 0, right = 0, zero = 0; right < nums.size(); right++)
		 {
			 if(nums[right] == 0) zero++; // 进窗⼝
			 while(zero > k) // 判断
			 	if(nums[left++] == 0) zero--; // 出窗⼝
			 ret = max(ret, right - left + 1); // 更新结果
		 }
		 return ret;
	 }
};

将 x 减到 0 的最小操作数

题目描述：给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int len=INT_MAX;
        int left=0;
        int right=0;
        int sum=0;
        while(left<nums.size())    
        {
            if(left==right%nums.size()&&right>=nums.size())
            {
                break;
            }
            sum+=nums[right%nums.size()];
            while(sum>x&&left<nums.size())
            {
                sum-=nums[left++];
            }
            if(sum==x&&left<nums.size())
            {
                if(0==left||right+1>=nums.size())
                {
                    len=min(len,right-left+1);
                }
                sum-=nums[left++];
            }
            ++right;
        }

        return len==INT_MAX?-1:len;
    }
};

class Solution
{
public:
 int minOperations(vector<int>& nums, int x) 
 {
	 int sum = 0;
	 for(int a : nums) sum += a;
	 int target = sum - x;
	 // 细节问题
	 if(target < 0) return -1;
	 int ret = -1;
	 for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
	 {
		 tmp += nums[right]; // 进窗⼝
		 while(tmp > target) // 判断
		 	tmp -= nums[left++]; // 出窗⼝
		 if(tmp == target) // 更新结果
		 	ret = max(ret, right - left + 1);
	 }
	 if(ret == -1) return ret;
	 else return nums.size() - ret;
 }
};

水果成篮

题目描述：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        vector<vector<int>> backet(2,vector<int>(2,0));
        int maxSum=0;
        int left1=0;
        int left2=0;
        int cur=0;
        while(cur<fruits.size()){
            if(fruits[cur]!=fruits[0]){
                break;
            }
            ++cur;
        }
        left1=cur-1;
        left2=cur;
        int right=cur;
        backet[0][0]=fruits[0];
        backet[0][1]=cur;
        if(cur<fruits.size()){
            backet[1][0]=fruits[cur];
        }
        while(right<fruits.size()){

            if(fruits[right]==backet[0][0]){
                ++backet[0][1];
                left1=right;
            }else if(fruits[right]==backet[1][0]){
                ++backet[1][1];
                left2=right;
            }
            else {
                if(maxSum<backet[0][1]+backet[1][1]){
                    maxSum=backet[0][1]+backet[1][1];
                }
                if(left1<left2){
                    backet[1][1]=left2-left1;
                    backet[0][0]=fruits[right];
                    backet[0][1]=1;
                    left1=right;
                }
                else{
                    backet[0][1]=left1-left2;
                    backet[1][0]=fruits[right];
                    backet[1][1]=1;
                    left2=right;
                }
            }
            ++right;   
        }
        if(maxSum<backet[0][1]+backet[1][1]){
            maxSum=backet[0][1]+backet[1][1];
        }

        return maxSum;
    }
};

class Solution
{
public:
 int totalFruit(vector<int>& f) 
 {
	 unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果
	 int ret = 0;
	 for(int left = 0, right = 0; right < f.size(); right++)
	 {
		 hash[f[right]]++; // 进窗⼝
		 while(hash.size() > 2) // 判断
		 {
			 // 出窗⼝
			 hash[f[left]]--;
			 if(hash[f[left]] == 0)
			 hash.erase(f[left]);
			 left++;
		 }
		 ret = max(ret, right - left + 1);
	 }
	 return ret;
 }
};

找到字符串中所有字母异位词

题目描述：给定两个字符串 s 和 p，找到 s 中所有 p 的
异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> originCount(128,-1);
        vector<int> curCount(128,0);
        int count=0;
        int i=0;
        for(;i<p.size();++i){
            if(-1==originCount[p[i]]){
                originCount[p[i]]=1;
            }else{
                originCount[p[i]]++;
            }
        }
        int left=0;
        int right=0;
        vector<int> ans;
        for(;right<s.size();++right){
            if(-1==originCount[s[right]]){
                curCount=vector<int>(128,0);
                left=right+1;
                count=0;
            }else{
                if(curCount[s[right]]<originCount[s[right]]){
                    ++curCount[s[right]];
                    ++count;
                }else{
                    for(;left<right;++left){
                        if(s[left]==s[right]){
                            ++left;
                            break;
                        }
                        --count;
                        curCount[s[left]]--;
                    }
                }
            }
            if(count==p.size()){
                ans.push_back(left);
            }
        }

        return ans;
    }
};

class Solution
{
public:
 vector<int> findAnagrams(string s, string p) 
 {
	 vector<int> ret;
	 int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
	 for(auto ch : p) hash1[ch - 'a']++;
	 int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
	 int m = p.size();
	 for(int left = 0, right = 0, count = 0; right < s.size(); right++)
	 {
		 char in = s[right];
		 // 进窗⼝ + 维护 count
		 if(++hash2[in - 'a'] <= hash1[in - 'a']) count++; 
		 if(right - left + 1 > m) // 判断
		 {
			 char out = s[left++];
			 // 出窗⼝ + 维护 count
			 if(hash2[out - 'a']-- <= hash1[out - 'a']) count--; 
		 }
		 // 更新结果
		 if(count == m) ret.push_back(left);
	 }
	 return ret;
 }
};

串联所有单词的子串

题目描述：给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> originCount;
        for(auto& e:words){
            originCount[e]++;
        }
        int start=0;
        vector<int> ans;
        for(;start<words[0].size();++start){
            unordered_map<string,int> curCount;
            if(start+words[0].size()*words.size()>s.size()){
                break;
            }
            int i=start;
            int j=start;
            int count=0;
            while(true){
                string tmp=s.substr(i,words[0].size());
                if(tmp.size()!=words[0].size()){
                    break;
                }
                if(originCount.end()==originCount.find(tmp)){
                    curCount=unordered_map<string,int>();
                    count=0;
                    j=i+words[0].size();
                }
                else{
                    if(curCount[tmp]<originCount[tmp]){
                        ++count;
                        ++curCount[tmp];
                    }else{
                        while(true){
                            string t=s.substr(j,words[0].size());
                            if(t==tmp){
                                j+=words[0].size();
                                break;
                            }
                            --count;
                            curCount[t]--;
                            j+=words[0].size();
                        }
                    }
                }

                if(count==words.size()){
                    ans.push_back(j);
                }
                i+=words[0].size();
            }
        }

        return ans;
    }
};

class Solution
{
public:
 vector<int> findSubstring(string s, vector<string>& words) 
 {
	 vector<int> ret;
	 unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
	 for(auto& s : words) hash1[s]++;
	 int len = words[0].size(), m = words.size();
	 for(int i = 0; i < len; i++) // 执⾏ len 次
	 {
		 unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
		 for(int left = i, right = i, count = 0; right + len <= s.size(); 
		right += len)
		 {
			 // 进窗⼝ + 维护 count
			 string in = s.substr(right, len);
			 hash2[in]++;
			 if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
			 // 判断
			 if(right - left + 1 > len * m)
			 {
				 // 出窗⼝ + 维护 count
				 string out = s.substr(left, len);
				 if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
				 hash2[out]--;
				 left += len;
			 }
			 // 更新结果
			 if(count == m) ret.push_back(left);
		}
	  }
	 return ret;
 }
};

最小覆盖子串

题目描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> originCount(128,-1);
        vector<int> curCount(128,0);
        int i=0;
        for(;i<t.size();++i){
            if(-1==originCount[t[i]]){
                originCount[t[i]]=1;
                continue;
            }
            originCount[t[i]]++;
        }
        string ans;
        int left=0;
        int right=0;
        int count=0;
        for(;left<s.size();++left){
            if(-1!=originCount[s[left]]){
                break;
            }
        }
        right=left;
        for(;right<s.size();++right){
            if(-1==originCount[s[right]]){
                continue;
            }
            if(curCount[s[right]]<originCount[s[right]]){
                ++count;
            }
            curCount[s[right]]++;

            if(count==t.size()){
                printf("%d %d\n",left,right);
                while(true){
                    if(-1==originCount[s[left]]){
                        ++left;
                        continue;
                    }else if(curCount[s[left]]>originCount[s[left]]){
                        curCount[s[left]]--;
                        ++left;
                        continue;
                    }
                    break;
                }
                if(ans.empty()||ans.size()>right-left+1){
                    ans=s.substr(left,right-left+1);
                }
            }
        }

        return ans;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0;        // 统计有效字符有多少种
        for (auto ch : t)
            if (hash1[ch]++ == 0)
                kinds++;
        int hash2[128] = {0}; // 统计窗⼝内每个字符的频次
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in])
                count++;           // 进窗⼝ + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out])
                    count--; // 出窗⼝ + 维护 count
            }
        }
        if (begin == -1)
            return "";
        else
            return s.substr(begin, minlen);
    }
};