本次作业完成了力扣《面试经典 150 题》「滑动窗口」部分的全部题目。

力扣 面试经典 150 题 - 滑动窗口

LeetCode 209. 长度最小的子数组

思路

按照最暴力的方法来说，枚举数组中所有的区间和，然后统计满足条件的最短区间即可，这样的算法复杂度为 $\mathrm O(n ^ 2)$。

但我们不难注意到，当 $l$ 一定时，所有满足 $\sum_{i=l}^r nums[i] \ge target$ 的 $r$ 只有最小的那一个对答案产生了贡献，而后面更大的 $r$ 完全可以不进行遍历；同样地，当 $r$ 一定时，所有满足 $\sum_{i=l}^r nums[i] \ge target$ 的 $l$ 只有最大的那一个对答案产生了贡献，但更小的 $l$ 的遍历则较难跳过。于是我们从 $r$ 入手，每次循环在固定 $r$ 的情况下，找到满足条件的最大的 $l$，此时我们可以观察到，如果 $[l, r]$ 是对于 $r$ 来说满足条件的最小区间（最大的 $l$），则 $[l, r + 1]$ 一定也满足条件，因此当我们发现 $[l, r]$ 对于 $r$ 来说是满足条件的最小区间后，下次对于 $r + 1$ 的循环的直接从 $l + 1$ 开始检查即可，这样便实现了对于前面更小的 $l$ 都不（在该轮循环）进行遍历。这样虽然看起来是两重循环，但 $l$ 和 $r$ 都只会右移，$l$ 并不会重新开始计数，因此算法复杂度为 $\mathrm O(n)$，这种算法一般被称为“滑动窗口”。

代码

提交记录：24 ms (96.58%) / 27.19 MB (60.62%)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = nums.size() + 1, l = 0, r = 0, now = 0;
        for (r <= nums.size(); now += (r++ == nums.size() ? 0 : nums[r - 1]))
            while (now >= target) ans = min(ans, r - l), now -= nums[l++];
        return ans == nums.size() + 1 ? 0 : ans;
    }
};

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

思路

套用上一题的思路，直接采用滑动窗口即可解决此题。需要注意的是，对于无重复字符的判断这一问题，因为值域只有 $char$ 类型的数据范围，因此我们直接开一个同样大的布尔数组来记录是否出现过即可。

代码

提交记录：8 ms (91.02%) / 6.90 MB (92.36%)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, l = 0, cnt[128] = {0};
        for (int i = 0; i < s.length(); ++i)
            if (cnt[s[i]])
            {
                while(s[l] != s[i]) --cnt[s[l++]];
                ans = max(ans, i - (l++));
            }
            else ++cnt[s[i]], ans = max(ans, i - l + 1);
        return ans;
    }
};

LeetCode 30. 串联所有单词的子串

思路

注意到一个非常特别的性质是 $words$ 中所有字符串长度都相同，这样我们便可以直接将 $s$ 切分成 $\lfloor{ len_s\over len_{word}}\rfloor$ 个字符串，然后再将 $words$ 在上面使用滑动窗口算法匹配，这一过程的复杂度为 $\mathrm O(\lfloor{ len_s\over len_{word}}\rfloor)$，而 $s$ 的切分方式有 $len_{word}$ 种，因此总复杂度为 $\mathrm O(\lfloor{ len_s\over len_{word}}\rfloor \times len_{word}) = \mathrm O(len(s)) $。实现上，我们可以用 unordered_map 来记录字符串需要匹配的次数和当前匹配的次数，来尽量快地进行字符串的匹配。

代码

提交记录：28 ms (97.71%) / 17.41 MB (93.92%)

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        unordered_map<string, int> targetMap;
        if (s.size() <= 0 || words.empty()) return res;
        int wordSize = words[0].size(), numWords = words.size();
        for (string& word : words) ++targetMap[word];
        for (int i = 0, left = 0, right = 0, cnt = 0; i < wordSize; left = right = ++i, cnt = 0)
        {
            unordered_map<string, int> currMap;
            while (right + wordSize <= s.size())
            {
                string currWord = s.substr(right, wordSize);
                right += wordSize;
                if (targetMap.find(currWord) != targetMap.end())
                {
                    ++currMap[currWord], ++cnt;
                    while (currMap[currWord] > targetMap[currWord]) --currMap[s.substr(left, wordSize)], left += wordSize, --cnt;
                    if (cnt == numWords) res.push_back(left);
                }
                else left = right, cnt = 0, currMap.clear();
            }
        }
        return res;
    }
};