刷刷刷——滑动窗口

文章目录

• 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

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

简易哈希表：

class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        //unordered_map 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

对比：

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

这里每次都要比较哈希表，复杂度其实是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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

对比

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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37