leetcode中几道与维护窗口相关的问题

leetcode中有几道题使用同一个思路，大致是先维护一个窗口，每次只移动窗口左侧或者右侧的边界，然后针对这个窗口内的元素进行处理。这种方式使用两个指针，可以将问题的运行时间降到O(n)内。

 

Longest Substring Without Repeating Characters：https://leetcode.com/problems/longest-substring-without-repeating-characters/

这道题我们维护一个窗口，每次将右边的窗口向前移动一位。另外维护一个hash表，标记当前窗口中的字符的位置，一旦右边的窗口遇到了当前窗口中的字符，说明有重复，将左边窗口移到当前窗口中重复字符的下一位，更新重复字符的位置为有窗口的位置。每次移动右窗口都更新当前的最大长度，知道有窗口移到最后一位。

这里hash table有一个对于字符串常用的用法，就是声明一个长度为256的数组，正好对应256个字符。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> visit(256, -1);
        int start = 0, end = 0, len = 0;
        while(end < s.length()) {
            if(visit[s[end]] >= start) {
                start = visit[s[end]] + 1;
            }
            visit[s[end]] = end;
            len = max(end + 1 - start, len);
            end++;
        }
        return len;
    }
};

 

substring with concatenation of all words leetcode：https://leetcode.com/problems/substring-with-concatenation-of-all-words/

这道题的思路也是维护一个窗口和hash表。但是由于这道题的特殊性，需要维护两个hash，一个是不能改变的hash，用来存储字典；另一个是会变化的，都用来存储当前的窗口中访问的word以及每个word访问的次数。

为了是算法在O(n)时间内运行，这里还有一个技巧，（这个技巧也是使得这道题更难的原因），假设源字符串的长度为n，字典中单词的长度为wlen。因为不是一个字符，所以我们需要对源字符串所有长度为wlen的子串进行判断。做法是i从0到wlen-1个字符开始，得到初始考察的end为i, i+wlen, i+2*wlen, ...的长度为wlen的单词。这样就可以保证判断到所有的满足条件的串。因为每次扫描的时间复杂度是O(2*n/wlen)(每个单词不会被访问多于两次，一次是窗口右端，一次是窗口左端)，总共扫描l次（i=0, ..., wlen-1)，所以总复杂度是O(2*n/l*l)=O(n)，是一个线性算法。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> stable_dict;
        for(int i = 0; i < words.size(); i++) {
            if(stable_dict.find(words[i]) == stable_dict.end())
                stable_dict.insert(make_pair(words[i], 1));
            else
                stable_dict[words[i]]++;
        }
        vector<int> res;
        int wlen = words[0].size();
        int i = 0;
        while(i < wlen) {
            int end = i;
            int start = i;
            int count = 0;
            unordered_map<string, int> dict;
            while(end < s.length()) {
                string cur = s.substr(end, wlen);
                string start_cur = s.substr(start, wlen);
                if(stable_dict.find(cur) != stable_dict.end()) {
                    if(dict.find(cur) == dict.end())
                        dict.insert(make_pair(cur, 0));
                    if(dict[cur] < stable_dict[cur]) {
                        dict[cur]++;
                        count++;
                        end += wlen;
                    }
                    else {
                        if(count == words.size()) 
                            res.push_back(start);
                        dict[start_cur]--;
                        count--;
                        start += wlen;
                    }
                }
                else {
                    end += wlen;
                    count = 0;
                    start = end;
                    dict.clear();
                }
            }
            i++;
        }
        return res;
    }
};

 

Minimum Window Substring: https://leetcode.com/problems/minimum-window-substring/

这道题的思路和上一道很相似。区别是每次循环都要右移右指针，而移动左指针的条件是当所有的字典中的字符都在窗口中，停止移动的条件是有字符不在窗口中。这里要注意的一点是由于我们采取了纪录所有出现在窗口中的字典中字符的个数，所以如果某个字符的这个个数比字典中应有的个数多，也应当让左指针移动，并且减少这个值直到和字典的字符数一样多。

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        int start = 0, end = 0;
        int count = 0;
        vector<int> record(256, 0);
        vector<int> dict(256, 0);
        for(int i = 0; i < t.length(); i++) {
            dict[t[i]]++;
        }
        while(end < s.length()) {
            if(dict[s[end]] > 0) {
                record[s[end]]++;
                if(record[s[end]] <= dict[s[end]]) {
                    count++;
                }
                if(count == t.length()) {
                    while(dict[s[start]] == 0 || record[s[start]] > dict[s[start]]) {
                        record[s[start]]--;
                        start++;
                    }
                    res = res.length() == 0 ? s.substr(start, end + 1 - start) : res.length() < (end + 1 - start) ? res : s.substr(start, end + 1 - start);
                    record[s[start]]--;
                    count--;
                    start++;
                }
            }
            end++;
        }
        return res;
    }
};

 

Minimum Size Subarray Sum: https://leetcode.com/problems/minimum-size-subarray-sum/

这道题也是用一个窗口，在窗口中的数的和小于s的时候移动右窗口，否则考察当前的子数组是否最小， 并移动左窗口。这道题比之前几道题更简单是因为这里不需要hash table去存窗口信息，只需一个int存窗口中数的和即可。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int start = 0, end = 0, len = nums.size() + 1, sum = 0;
        while(end < nums.size() || sum >= s) {
            if(sum < s) {
                sum += nums[end];
                end++;
            }
            if(sum >= s) {
                sum -= nums[start];
                len = min(len, end - start);
                start++;
            }
        }
        return len == nums.size() + 1 ? 0 : len;
    }
};

 

可以看出这类窗口的问题其实是双指针扫描，关键点是判断两个指针的移动条件以及考虑使用hash table等额外保存窗口内元素的信息。