算法专题二: 滑动窗口

1. 长度最小的子数组

题目思路:

首先暴力解法就是依次枚举出所有的子数组, 从第一个元素为左端点依次向后枚举, 枚举到长度大于target就停止枚举, 以第二个元素为左端点进行枚举, 这里我们可以进行优化.

滑动窗口解法, 定义两个下标, left先从第一个元素位置开始, right找右端点, 如果找到了此时right也不需再回到第二个元素开始, 和left一起向后走, 因为我们已经计算出right- left这段区间的和了, 只需要减去第一个元素即可枚举下一个数组, 并且right前一个元素与前面元素之和我们已经知道一定是小于target的, 所以直接left++即可, 这种场景就像在维持一个滑动窗口一样, 同向双指针, 按照以下步骤我们进行编写代码.

编写代码:

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

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

题目思路:

首先看到求子串子数组, 我们首先可以想到滑动窗口, 但是怎么判断不重复呢, 我们可以利用哈希, 但是没必要使用容器, 因为字符范围我们已经知道了, 所以自己创建一个, 进窗口, 就是把每个字符扔到哈希表里, 判断条件就是是否重复, 如果重复, 那就出窗口进行下一次判断, 最后判断结束之后更新结果.

编写代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0},ret = 0;
        for(int left = 0, right = 0; right < s.size(); right++)
        {
            hash[s[right]]++;
            while(hash[s[right]] == 2)
            {
                hash[s[left]]--;
                left++;
            }
            ret = max(ret, (right - left +1));
        }
        return ret;
    }
};

3. 最大连续1的格数Ⅲ

题目思路:

寻找最大连续1的个数, 进窗口, 如果是1, 无视, 如果是0 ,则计数器加1, 当计数器大于k时, 开始判断然后出窗口, 最后更新结果.

编写代码:

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

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

题目思路:

采用正难则反的思想, 转化为找出最长子数组的长度, 所有元素之和正好等于sum- x即可, 然后进行滑动窗口求解, 最后更新结果时需要判断.

编写代码:

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0, ret = -1;
        for(const auto& e : nums) sum+=e;
        int target = sum - x;
        if(target < 0) return -1;
        int tmp = 0;
        for(int left = 0, right = 0; right  < nums.size(); right++)
        {
            tmp += nums[right];
            while(tmp > target)
            {
                tmp -= nums[left];
                left++;
            }
            if(target == tmp)
                ret = max(ret, (right - left + 1));
        }
        if(ret == -1) return ret;
        else return nums.size() - ret;
    }
};

5. 水果成篮

题目思路:

采用暴力解法会超时, 我们采用滑动窗口解法, 定义kinds表示篮子的个数, 每次采摘水果之后将水果扔到哈希表中, 判断条件为如果种类大于2则出窗口, 并且把水果出哈希表, 进行下一次判断. 最后更新结果.

编写代码:

class Solution {
public:
    int totalFruit(vector<int>& f) {
        int hash[100001] = {0}, count = 0, ret = 0;
        for(int left = 0, right = 0; right < f.size(); right++)
        {
            if(hash[f[right]]++ == 0) count++;
            while(count > 2)
            {
                if(--hash[f[left++]] == 0) count--;
            }
            ret = max(ret,(right - left +1));
        }
        return ret;
    }
};

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

题目思路:

利用哈希表进行判断是否时异位词, 如果出现的次数都一样则为异位词, 利用变量count来记录有效字符的个数, 条件是, 进入哈希表之后判断 hash2[in] <= hash1[in] 是否成立, 如果成立则count++, 然后进行单次判断, 因为这里窗口大小一定是固定大小的, 所以判断长度是否合法,然后出窗口, 出窗口之前一样先更新count, 最后判断如果count等于p的长度则更新结果.

编写代码:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0}, hash2[26] = {0};
        vector<int> v;
        for(const auto& ch : p) hash1[ch - 'a']++;
        for(int left = 0,right = 0,count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if((right - left + 1) > p.size())
            {
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            if(count == p.size()) v.push_back(left);
        }
        return v;
    }
};

7. 串联所有单词的子串

题目思路:

这道题与上一道题的解法非常的类似, 只不过这里判断是字符串, 这里我们采用容器哈希表来求解, 移动的步长是单词的长度, 滑动窗口执行的次数为len.

编写代码:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash1;
        vector<int> ret;
        for(const auto& s : words) hash1[s]++;
        size_t len = words[0].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);
                if(hash1.count(in) && ++hash2[in] <= hash1[in]) count++;
                if((right - left + 1) > words.size() * len)
                {
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out]-- <= hash1[out]) count--;
                    left+=len;
                }
                if(count == words.size()) ret.push_back(left);
            }
        }
        return ret;
    }
};

8. 最小覆盖子串

题目思路:

寻找最小覆盖的子串, 这里有可能子串中存在多个t中的字符, 所以我们需要统计种类, 也就是有效个数的种类, 只有当hash1[in] == hash2[in]时, 我们才算做一次有效字符.

编写代码:

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; int kids = 0;
        for(const auto& ch : t)
            if(hash1[ch]++ == 0) kids++;
        int hash2[128] = {0};
        int begin = -1,len = INT_MAX;
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            //进窗口+维护
            if(++hash2[s[right]] == hash1[s[right]]) count++;
            while(count == kids)
            {
            if (right - left + 1 < len)
            {
                begin = left;
                len = right - left + 1;
            }
                if(hash2[s[left]]-- == hash1[s[left]]) count--;
                hash2[s[left++]];
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin,len);

    }
};

完