b站链接：https://www.bilibili.com/video/BV1hd4y1r7Gq/?spm_id_from=333.999.0.0&vd_source=738644d63e97553d6e3dc1cd66a642d6

OJ刷题总结3

本期视频介绍了三类典型的滑动窗口题目：最短/最长/方案数，代表题目分别为209, 3, 713

Leetcode 209

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续 子数组

$[nums_l, nums_l+1, …, nums_r-1, nums_r]$ ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

看到这题时，最的朴素的做法就是2层for循环，遍历去找答案。时间复杂度为$O(n^2)$.

但是，题目说，数组全部是由正整数组成的。这个性质很重要。这意味着什么呢？？

我们先看一个例子，

target = 7, nums = [2, 3, 1, 2, 4, 3]

我们先用朴素的2层for循环看这个例子。固定右端点，移动左端点，寻找当前最短的子数组。

假设说，我们当前的右端点指向数组第四个数字，2；此时，左端点指向第一个数字，2。当前的总和为8。右端点向右移动一个，由于我们的数组全部都是正整数组成的，所以，当我们右指针向右移动一格后，总和肯定还是会大于8.因此，此时左端点就没有必要重新再枚举了。左端点只用不断的往右走，直到不满足cur_sum - nums[left] >= 7（解释下这个判断条件，首先，我们明确一点，cur_sum >= 7，因为之前是 >= 7的，我们在做的是不断的减去 nums[left++]，找到一个紧的界使得cur_sum - nums[left] < 7.而这个界就是这个判断条件）。左端点是不用往左走的（往左走，由于数组全是正整数，只会让cur_sum越来越大。），所以左端点的遍历是O(n)的，这就大大的节约了时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int s = 0;
        int left = 0;
        int right = 0;
        int n = nums.size();
        int ans = n + 1;
        for (; right < n; right ++) {
            s += nums[right];
            // 当right固定时，left++，s减小，这就是单调性
            // 从满足要求到不满足要求
            while(s - nums[left] >= target) {
                s -= nums[left];
                left ++;
            }
            if (s >= target) ans = min(ans, right - left + 1);
        }
        return ans <= n ? ans : 0;
    }
};

需要解释下，为什么for循环中的while循环不用加left <= right。假设说，当left=right了，这时s - nums[left]是不是就等于0了？target的数据范围是1 <= target <= 1e9，是不是就一定 s - nums[left] < target了，跳出while循环。

Leetcode 3

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

思路其实是一样的，只是这里我们的left指针的移动，是从不满足移动到不满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int left = 0, right = 0;
        int n = s.size();
        unordered_map<char, int> hash;
        for (; right < s.size(); right++) {
            hash[s[right]] ++;
            while (hash[s[right]] > 1) {
                hash[s[left]] --;
                left ++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

Leetcode 713

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

这题和第二题很像，虽然说题目是找所有子数组的数目，但是实际上，是要找固定右端点，左端点最左能到哪？

为什么呢？nums的数据范围：1 <= nums[i] <= 1000，全部都是正数，这说明只要找到了最左的边界，那么在[left, right-1]的点都能当左端点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int n = nums.size();
        int cheng = 1;
        int ans = 0;
        int left = 0, right = 0;
        for (; right < n; right ++) {
            cheng *= nums[right];
            while (cheng >= k) {
                cheng /= nums[left];
                left ++;
            }
            if (cheng < k) {
                ans += right - left + 1;
            }
        }
        return ans;
    }
};

Leetcode 2958

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

这题和Leetcode 3很像，不赘述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int ans = 0;
        int n = nums.size();
        unordered_map<int, int> hash;
        int left = 0, right = 0;
        for (; right < n; right ++) {
            hash[nums[right]] ++;
            while (hash[nums[right]] > k) {
                hash[nums[left]] --;
                left ++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

Leetcode 2730

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，0010 、002020 、0123 、2002 和 54944 是半重复字符串，而 00101022 和 1101234883 不是。

请你返回 s 中最长 半重复 子字符串的长度。

一个 子字符串 是一个字符串中一段连续 非空 的字符。

也是很类似的，和Leetcode 3，Leetcode 2958.

但是需要注意，怎么判断从一个不满足状态到满足的状态。

题目说，一个子字符串最多有一个一对相邻字符相等。说明不满足状态是有2对相邻字符相等。

从不满足状态到满足状态的过程，也就是left++后，被“抛弃掉的字符”与当前left指向的字符相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int k = 0;
        int n = s.size();
        int left = 0, right = 0;
        int ans = 0;
        for (; right < n; right ++) {
            if(right > 0 && s[right] == s[right - 1]) {
                k ++;
            }
            if (k == 2) {
                left ++;
                while (s[left] != s[left - 1]) {
                    left ++;
                }
                k --;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

Leetcode 1004

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

这题转了个弯，本质上是求一个nums数组中最多有k个0，其最长长度为多少？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = 0;
        int ans = 0;
        int cur_0 = 0;
        for (; right < n; right ++) {
            cur_0 += nums[right] == 0;
            if (cur_0 > k) {
                left ++;
                while (nums[left - 1] != 0) left ++;
                cur_0 -= 1;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

Leetcode 2962

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

本质是求至少出现k次的子数组，最短是多少？

遍历right，得到每个right对应的最大left（等价于最短的子数组长度）。

问自己一个问题，如果当前最大的left满足，是不是对于任意的 i < left，组成的数组[i, right] 都是满足的呢，对吧？

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
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int total_max = 0;
        int n = nums.size();
        for (int i = 0; i < n; i ++) {
            total_max = max(total_max, nums[i]);
        }

        int left = 0, right = 0;
        int cur_cnt = 0;
        long long ans = 0;
        for (; right < n; right ++) {
            if (nums[right] == total_max) {
                cur_cnt ++;
            }
            if (cur_cnt == k) {
                left ++;
                while (nums[left - 1] != total_max) {
                    left ++;
                }
                cur_cnt --;
            }
            ans += left;
        }
        return ans;
    }
};

Leetcode 1658

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

逆向思维，等价于找到一个最长的子数组，使其和为 s - x

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
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 逆向思维
        // 找到一个最长的子数组，使其和为 s - x
        int n = nums.size(); 
        int left = 0, right = 0;
        int ans = -1;
        int sum = 0;
        for (int i = 0; i < n; i ++) {
            sum += nums[i];
        }
        sum = sum - x;
        if (sum < 0)    return -1;
        int cur_sum = 0;
        for (; right < n; right ++) {
            cur_sum += nums[right];
            while (cur_sum > sum) {
                cur_sum -= nums[left ++];
            }
            if (cur_sum == sum) {
                ans = max(ans, right - left + 1);
            }
        }
        return ans == -1 ? -1 : n - ans;
    }
};

Leetcode 76

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

这题需要我们判断一下，s的子串是否包含了t的所有字符。一个朴素的做法是遍历t，判断每一个字符是否都比s子串的少。

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
class Solution {
public:
    unordered_map<char, int> hash_s;
    unordered_map<char, int> hash_t;

    bool check() {
        for (auto item : hash_t) {
            if (hash_s[item.first] < hash_t[item.first]) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (int i = 0; i < t.size(); i ++) {
            hash_t[t[i]] ++;
        }
        int n = s.size();
        int left = 0, right = 0;
        int cur_len = n;
        string ans = "";
        for (; right < n; right ++) {
            hash_s[s[right]] ++;
            if (check()) {
                while(hash_s[s[left]] > hash_t[s[left]]) {
                    hash_s[s[left ++]] --;
                }
                if (cur_len >= right - left + 1) {
                    cur_len = right - left + 1;
                    ans = "";
                    for (int i = left; i <= right; i ++) {
                        ans += s[i];
                    }
                }
            }
        }
        return ans;
    }
};

但其实没必要每次都遍历整个t。当我们有一次成功包含了t的所有字符，后面就必要再去遍历了。
可以用一个less变量来存还有多少个t的字符没有被包含。

更新条件是：

1
less -= hash_s[s[right]] == hash_t[s[right]];

当less==0时，说明包含成功！

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
class Solution {
public:
    unordered_map<char, int> hash_s;
    unordered_map<char, int> hash_t;

    string minWindow(string s, string t) {
        for (int i = 0; i < t.size(); i ++) {
            hash_t[t[i]] ++;
        }
        int n = s.size();
        int left = 0, right = 0;
        int cur_len = n;
        int less = hash_t.size();
        string ans = "";
        for (; right < n; right ++) {
            hash_s[s[right]] ++;
            less -= hash_s[s[right]] == hash_t[s[right]];
            if (less == 0) {
                while(hash_s[s[left]] > hash_t[s[left]]) {
                    hash_s[s[left ++]] --;
                }
                if (cur_len >= right - left + 1) {
                    cur_len = right - left + 1;
                    ans = "";
                    for (int i = left; i <= right; i ++) {
                        ans += s[i];
                    }
                }
            }
        }
        return ans;
    }
};