Sliding Window

sliding window: 解决数组/字符串的子元素问题，它可以将嵌套循环问题，转换为单循环问题，降低时间复杂度.

总结一下Leetcode上sliding window的一些问题

 最简单的sliding window问题：给定一个整数数组，计算长度为 k 的连续子数组的最大总和

int maxSum(vector<int>& arr, int k){
    int max_sum = 0;
    for(int i = 0; i < k; ++i)
        max_sum += arr[i];
    int window_sum = max_sum;
    for(int i = k; i < arr.size(); ++i){
        window_sum += arr[i] - arr[i - k];
        max_sum = max(max_sum, window_sum);
    }
    return max_sum;
}

Leetcode 3. Longest Substring Without Repeating Characters

给定一个字符串，计算不包含重复字母的字串的最大长度

 分析：用一个map，key是字母，value是字母的位置，两个指针 i, j 指向当前窗口的头和尾，如果map[s[i]] > j，说明当前窗口内已经出现过一次 s[i] 了，此时 j 移动到 map[s[i]]，同时，当前字母的位置要存入map中。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //时间复杂度O(n), 空间复杂度O(m), m是字符集的大小
        int n = s.size(), res = 0;
        //如果是任意字符，则用map<char, int>, 如果只有字母，可用vector<int>(128)
        vector<int> index(128);
        for(int i = 0, j = 0; i < n; ++i){
            //j是窗口的开始位置，i是窗口的当前位置
            //如果s[i]从未出现过，index[s[i]] = 0, j保持开始位置不变;
            //如果s[i]出现过，且在当前窗口内，则index[s[i]] > j, index[s[i]]表示s[i]第一次出现的位置+1，j = index[s[i]];
            //如果s[i]出现过，但不在当前窗口内，则index[s[i]] < j, j保持开始位置不变
            j = max(index[s[i]], j);
            //i - j - 1是当前窗口大小
            res = max(res, i - j + 1);
            //记录当前字符的位置
            index[s[i]] = i + 1;
        }
        return res;
    }
};

Leetcode 76. Minimum Window Substring

给定一个字符串S和字符串T，在S中找出包含T所有字母的最小字串，要求time O(n)

class Solution {
public:
    string minWindow(string s, string t) {
        //1. Use two pointers: start and end to represent a window.
        //2. Move end to find a valid window.
        //3. When a valid window is found, move start to find a smaller window.
        //To check if a window is valid, we use a map to store (char, count) for chars in t.
        //And use counter for the number of chars of t to be found in s. The key part is m[s[end]]--;.
        //We decrease count for each char in s. If it does not exist in t, the count will be negative.
        vector<int> m(128, 0);
        for(char c : t) m[c]++;
        int start = 0, end = 0, d = INT_MAX, head = 0, counter = t.size();
        while(end < s.size()){
            if(m[s[end]] > 0) counter--;
            m[s[end]]--;
            end++;
            while(counter == 0){
                if(end - start  < d) {
                    d = end - start;
                    head = start;
                }
                if(m[s[start]] == 0) counter++;
                m[s[start]]++;
                start++;
            }
        }
        return d == INT_MAX ? "" : s.substr(head, d);
    }
};

Leetcode 239. Sliding Window Maximum

给定一个数组，一个大小为 k 的窗口从数组最左端开始滑动，每次向右滑动1，返回每个窗口中的最大值构成的数组。

分析：用deque存"promising element"

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for(int i = 0; i < nums.size(); ++i){
            if(!dq.empty() && dq.front() == i - k) dq.pop_front();
            while(!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if(i >= k - 1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};