刷刷刷——滑动窗口

在这里插入图片描述

文章目录

209. 长度最小的子数组（中等）
题目链接
算法原理
代码实现

3. 无重复字符的最长子串（中等）
题目链接
算法原理
代码实现

1004. 最大连续1的个数 III（中等）
题目链接
算法原理
代码实现

1658. 将 x 减到 0 的最小操作数（中等）
题目链接
算法原理
代码实现

904. 水果成篮（中等）
题目链接
算法原理
代码实现

438. 找到字符串中所有字母异位词（中等）
题目链接
算法原理
代码实现

30. 串联所有单词的子串（困难）
题目链接
算法原理
代码实现

76. 最小覆盖子串（困难）
题目链接
算法原理
代码实现

209. 长度最小的子数组（中等）

题目链接

209. 长度最小的子数组

算法原理

暴力枚举：

这里可以枚举出所有子数组的和，然后从中选出符合条件的，最后再选出长度最小的那组，这样的时间复杂度为O(N²)

滑动窗口：

代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int sz = nums.size();
        int ret = INT_MAX;
        int sum = 0;
        for(int left=0,right=0;right<sz;right++)
        {
            sum+=nums[right];
            while(sum>=target)
            {
                ret = min(ret,right-left+1);
                sum-=nums[left++];
            }
        }
        return ret==INT_MAX?0:ret;
    }
};

3. 无重复字符的最长子串（中等）

题目链接

3. 无重复字符的最长子串

算法原理

暴力枚举+哈希表：

每个位置都进行从前往后枚举，然后用哈希表统计是否出现了重复元素

滑动窗口：

在暴力枚举的思想上做出优化

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        int left = 0;
        int right = 0;
        int hash[128] = { 0 };
        int ret = INT_MIN;
        while(right<s.size())
        {
            //进窗口
            hash[s[right]]++;
            //值有重复，出窗口
            while(hash[s[right]]>1)
            {
                hash[s[left++]]--;
            }
            ret = max(ret,right-left+1);
            right++;
        }
        return ret==INT_MIN?0:ret;
    }
};

1004. 最大连续1的个数 III（中等）

题目链接

1004. 最大连续1的个数 III

算法原理

暴力枚举+0计数器

连续的1，再加上k个0

滑动窗口：

代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int left = 0;
        int right = 0;
        int zeroCount = 0;
        int ret = INT_MIN;
        while(right<nums.size())
        {
            if(nums[right] == 0)
                zeroCount++;
            
            while(zeroCount>k)
            {
                if(nums[left] == 0)
                    zeroCount--;
                left++;
            }
            ret = max(ret,right-left+1);
            right++;
        }
        return ret;
    }
};

1658. 将 x 减到 0 的最小操作数（中等）

题目链接

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

算法原理

思路转换：

找出最长的子数组长度，让这个子数组中元素的和正好等于sum-x（sum为整个数组的和），然后采用滑动窗口思想

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int left = 0;
        int right = 0;
        int len = INT_MIN;
        int arrSum=0;
        for(auto e:nums)
        {
            arrSum+=e;
        }
        int sum = 0;
        int target = arrSum-x;
        //target<0的话，滑动窗口就不适用
        if(target < 0)
            return -1;
        while(right<nums.size())
        {
            sum+=nums[right];
            while(sum>target)
            {
                sum-=nums[left];
                left++;
            }
            if(sum == target)
                len = max(len,right-left+1);
            right++;
        }
        return len==INT_MIN?-1:nums.size()-len;
    }
};

904. 水果成篮（中等）

题目链接

904. 水果成篮

算法原理

这里原始思路也是暴力枚举+哈希表，再原思路上作出优化，采用滑动窗口思想

代码实现

使用库里面的哈希表：

class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        unordered_map<int,int> mp;
        int ret = INT_MIN;
        int left = 0;
        int right = 0;
        while(right<fruits.size())
        {
            mp[fruits[right]]++;
            while(mp.size() > 2)
            {
                mp[fruits[left]]--;
                if(mp[fruits[left]] == 0)
                    mp.erase(fruits[left]);
                left++;
            }
            ret = max(ret,right-left+1);
            right++;
        }
        return ret==INT_MIN?0:ret;
    }
};

这里提交会发现，时间还是较长的，虽然量级是在O(N)，但因为这里涉及到哈希表的多次插入和删除，所以还是费些时间；

然后这里发现，题目给的数据范围有限：1 <= fruits.length <= 105，所以我们可以模拟哈希表的操作，自己造一个建议的哈希表

简易哈希表：

class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        //unordered_map<int,int> mp;
        int hash[100001] = { 0 };
        int ret = INT_MIN;
        int left = 0;
        int right = 0;
        int kinds = 0;
        while(right<fruits.size())
        {
            if(hash[fruits[right]] == 0)
                kinds++;
            hash[fruits[right]]++;
            while(kinds > 2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0)
                    kinds--;
                left++;
            }
            ret = max(ret,right-left+1);
            right++;
        }
        return ret==INT_MIN?0:ret;
    }
};

对比：

438. 找到字符串中所有字母异位词（中等）

题目链接

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

算法原理

滑动窗口+哈希表：

将字符丢入哈希表，然后当窗口大小等于p的大小的时候，开始判断这个哈希表是否相同

代码实现

class Solution
{
public:
    bool checkHash(int h1[], int h2[])
    {
        for (int i = 0, j = 0; i < 26; i++,j++)
        {
            if (h1[i] != h2[j])
                return false;
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p)
    {
        int left = 0;
        int right = 0;
        vector<int> ret;
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (auto e : p)
        {
            hash1[e - 97]++;
        }
        while (right < s.size())
        {
            hash2[s[right] - 97]++;
            if (right - left + 1 == p.size())
            {
                if (checkHash(hash1, hash2))
                    ret.push_back(left);
                hash2[s[left++] - 97]--;
                right++;
                continue;
            }

            right++;
        }
        return ret;
    }
};

这里每次都要比较哈希表，复杂度其实是O(26*N)，我们可以将比较方法改变一下

优化：

不对比哈希表，用count记录窗口有效字符的个数

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        int left = 0;
        int right = 0;
        vector<int> ret;
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (auto e : p)
        {
            hash1[e - 97]++;
        }
        int count = 0;
        while (right < s.size())
        {
            hash2[s[right] - 97]++;
            if(hash2[s[right]-97] <= hash1[s[right]-97])
                count++;

            if(right-left+1>p.size())
            {
                if(hash2[s[left]-97]<=hash1[s[left]-97])
                {
                    count--;
                }
                hash2[s[left++]-97]--;
            }
            if(count == p.size())
                ret.push_back(left);

            right++;
        }
        return ret;
    }
};

对比

30. 串联所有单词的子串（困难）

题目链接

30. 串联所有单词的子串

算法原理

采用438. 找到字符串中所有字母异位词的思路，将这些字符串看作字符

代码实现

class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
    vector<int> ret;
    unordered_map<string, int> hash1;
    for (auto e : words)
    {
        hash1[e]++;
    }
    int sz = s.size();
    int len = words[0].size();
    int m = words.size();
    for(int i =0;i<len;i++)
    {   
        int count = 0;
        unordered_map<string, int> hash2;
        for (int left = i, right = i; right < sz;)
        {
            string tmp = s.substr(right, len);
            hash2[tmp]++;
            //如果表1里面没有这个元素，就直接不比较了，避免又再临时去哈希表里面创建一个
            if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp])
                count++;

            if (right - left + 1 > m*len)
            {
                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);

            right += len;
        }
    }
    return ret;
}
};

76. 最小覆盖子串（困难）

题目链接

76. 最小覆盖子串

算法原理

哈希表+滑动窗口：

2个哈希表：一个放t的元素，然后统计有多少种元素；另一个用滑动窗口来放入元素，当这个哈希表中包含目标字符串，并且对应个数不小于目标串哈希表中各字符的个数时，那就可以更新这个窗口的大小

代码实现

class Solution
{
public:
    string minWindow(string s, string t)
    {
        int hash1[128] = { 0 };
        int kinds = 0;  //字符种类
        for(auto e:t)
        {
            if(hash1[e] == 0)
                kinds++;
            hash1[e]++;
        }
        int count = 0;
        int len = INT_MAX;
        int begin = -1;
        int hash2[128] = { 0 };
        for(int left=0,right=0;right<s.size();right++)
        {
            int in = s[right];
            if(++hash2[in] == hash1[in])
                count++;
            while(count == kinds)
            {
                if(right-left+1<len)
                {
                    len = right-left+1;
                    begin = left;
                }
                int out = s[left++];
                if(hash2[out]-- == hash1[out])
                    count--;
            }
        }
        return len==INT_MAX?"":s.substr(begin,len);
    }
};