算法专题二：滑动窗口

一.长度最小的子数组：

长度最小的子数组

1.思路一：暴力解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int num = 100000;
        int value = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += nums[j];
                if (sum >= target)
                {
                    value = sum;
                    if (value >= target && num >= (j - i + 1))
                    {
                        num = (j - i + 1);
                    }
                }
            }
        }

        if (num != 100000)
            return num;

        return 0;
    }
};

2.思路二：滑动窗口+双指针

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int len = INT_MAX;

        for(int left=0,right=0;right<nums.size();right++)
        {
            sum+=nums[right];
            while(sum>=target)
            {
                int len_1 = right-left+1;
                if(len_1 < len)
                    len = len_1;

                sum-=nums[left++];
            }
        }

        return (len==INT_MAX? 0 : len);
    }
};

3.GIF题目解析：

思路一：

思路二：

二.无重复字符的最长子串：

无重复字符的最长子串

1.思路一：滑动窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        int len = 0;
        int hash[128]={0};

        for(int left=0,right=0;right<s.size();right++)
        { 
            hash[s[right]]++;
            while(hash[s[right]]>1)
            {
                hash[s[left]]--;
                left++;  
            }
            len = max(len,(right-left+1));
        }

        return len;
    }
};

2.GIF题目解析：

思路一：

三.最大连续1的个数：

最大连续1的个数

1.思路一：滑动窗口

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int len = 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--;
            len = max(len,(right-left)+1);
        }
        return len;
    }
};

2.GIF题目解析：

开头位0 并且k为0算是一个特殊的情况这样的情况有一些考虑就走不出去前面的0而忽略到后面数组自带1，走不到这些1数据导致记录连续1的个数出问题！

四：将x减小到0的最小操作数：

将x减小到0的最小操作数

1.思路一：滑动窗口

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum_1 = 0;
        vector<int>::iterator it_1 = nums.begin();
        while (it_1 != nums.end())
        {
            sum_1 += (*it_1);
            it_1++;
        }
        
        int n = nums.size();
        int target = sum_1 - x;
        if(target <= 0)
        {
            if(target<0)
                return -1;
            else
                return n;
        }

        //1.滑动窗口：

        int sum_2 = 0;
        int ret = 0;

        for (int left = 0, right = 0; right < n; right++)
        {
            sum_2 += nums[right];
            while (sum_2 >= target)
            {
                if(sum_2 == target)
                    ret = max(ret, (right - left) + 1);

                sum_2 -= nums[left];
                left++;
            }
            if(sum_2 == target)
                ret = max(ret, (right - left) + 1);
        }
        return (ret==0? -1:n-ret);
    }
};

2.GIF题目解析：

五.水果成篮

水果成篮

1.思路一：滑动窗口

class Solution {
public:
    int totalFruit(vector<int>& fruits) {

        int Hash[100001]={0};
        int n = fruits.size();
        int len = 0;

        for(int left=0,right=0,zero=0;right<n;right++)
        {
            if(Hash[fruits[right]]==0)
            {
                Hash[fruits[right]]++;
                zero++;
            }
            else
            {
                Hash[fruits[right]]++;
            }

            while(zero > 2)
            {
                Hash[fruits[left]]--;

                if(Hash[fruits[left++]]==0)
                    zero--;
            }
            len = max(len , (right-left)+1);
        }

        return len;
    }
};

2.GIF题目解析：

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

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

1.思路一：滑动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26]={0};
        int len = p.size();
        for(auto ch:p)
        {
            hash1[ch -'a']++;
        }

        int hash2[26]={0};
        vector<int> vv;
        
        for(int left=0,right=0;right<s.size();right++)
        {
            hash2[s[right] - 'a']++;

            if((right-left+1) == len)
            {
                //1.判断是否相等
                int flag = 0;
                for(int i=0;i<26;i++)
                {
                    if(hash1[i] != hash2[i])
                    {
                        flag = -1;
                        break;
                    }
                }
                if(flag!=-1)
                    vv.push_back(left);
                
                hash2[s[left] - 'a']--;
                left++;
            }
        }
        return vv;
    }
};

2.思路二：滑动窗口（比较优化）

1.我们有注意到一个问题在比较相等确定left可不可以push的时候去优化一下26次循环比较的过程。
2.可以给一个变量去控制数量的变化。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26]={0};
        int len = p.size();
        for(auto ch:p)
        {
            hash1[ch -'a']++;
        }

        int hash2[26]={0};
        vector<int> vv;
        
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            //hash2[s[right] - 'a']++;
            if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
                count++;

            if((right-left+1) > len)
            {
                char out = s[left++];
                //出去窗口：
                if(hash2[out-'a']-- <= hash1[out-'a'])
                    count--;
            }
            if(count == len) vv.push_back(left);
        }
        return vv;
    }
};

2.GIF题目解析：

七.串联所有单词的子串

串联所有单词的子串

1.思路一：滑动窗口 + 哈希映射：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;

        unordered_map<string,int> hash1;
        for(auto& s:words)hash1[s]++;

        int len = words[0].size();
        int m  =words.size();

        for(int i=0;i<len;i++)//防止重复情况的出现
        {
            unordered_map<string,int> hash2;
            for(int left=i,right=i,count=0;right+len<=s.size();right+=len)
            {
                string in = s.substr(right,len);
                hash2[in]++;

                //1,进入窗口 + 维护count
                if(hash1.count(in) && hash2[in] <= hash1[in])
                    count++;
                
                if((right-left+1) > (len*m))
                {
                    //2.出去窗口 + 维护count
                    string out = s.substr(left,len);

                    if(hash1.count(out) && hash2[out] <= hash1[out])count--;
                    hash2[out]--;
                    left+=len;
                }

                //3.数据更新：
                if(count == m) ret.push_back(left);
            }
        }

        return ret;
    }
};

2.GIF题目解析：

八.最小覆盖子串

最小覆盖子串

1.思路一：暴力解法+哈希表

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for (char ch : t)
        {
            hash1[ch]++;
        }

        int kind = t.size();
        int len = INT_MAX;
        int begin = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int hash2[128] = { 0 };
            int count = 0;

            for (int j = i; j < s.size(); j++)
            {
                if (hash2[s[j]]++ < hash1[s[j]] && hash1[s[j]]!=0)
                    count++;

                if (kind == count)
                {
                    //更新数据：
                    if (j - i + 1 <= len)
                    {
                        len = j - i + 1;
                        begin = i;
                    }
                }
            }
        }

        string vv("");
        if (kind > s.size() || len == INT_MAX)
            return vv;

        vv = s.substr(begin, len);
        return vv;
    }
};

2.思路二：滑动窗口+哈希表

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        int kind = 0;
        for (char ch : t)
        {
            if(hash1[ch]++ == 0)
                kind++;
        }
        int len = INT_MAX;
        int begin = -1;
        int hash2[128] = { 0 };

        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            //1.进入窗口+维护count
            char in = s[right];
            if(++hash2[in] == hash1[in])
                count++;
            //2.判断出窗口+维护count
            while(count == kind)
            {
                if(right-left+1 < len)
                {
                    len = right-left+1;
                    begin = left;
                }

                char out = s[left++];
                if(hash2[out]-- == hash1[out])
                    count--;
            }
            
        }
        if(begin == -1)
            return "";
        else
            return s.substr(begin,len);
    }
};

2.GIF题目解析：