滑动窗口问题

leetcode 76.最小覆盖字串

begin从0开始，end从-1开始
注意vector<>.size()返回的是无符号整数
不能直接与int比较大小，尤其是存在负数的情况
假如窗口的下一个元素是目标字符串中的
先把下一个加入窗口
假如此时需要的字符数量超过了目标字符串的数量
试图前移开头，删除元素直到没有窗口中没有多余的字母为止

注意， 假如此时窗口中的该字符数量已经超过了需要的该字符数量，那就不能再增加已经cover的字符计数了，否则会导致错误

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> um, uTarget;
        int covered = 0;
        int n = s.size();
        for(int i = 0; i<t.size(); i++)
        {
            um[t[i]] = 0;
            if(!uTarget.count(t[i]))
            {
                uTarget[t[i]] = 1;
            }
            else
            {
                ++uTarget[t[i]];
            }
        }
        int begin = 0;
        int end = -1;
        int minBegin = 0, minEnd = 0, minLen = INT_MAX;
        // cout<<end<<"|"<<n-1<<endl;
        while(end<(n-1))
        {
            // cout<<'@'<<endl;
            if(um.count(s[end+1]))
            {
                if(um[s[end+1]]>=uTarget[s[end+1]])
                {

                    // ++covered;
                    ++um[s[++end]];
                    while(begin<end&&((!um.count(s[begin]))||(um[s[begin]]>uTarget[s[begin]])))
                    {
                        // cout<<'!';
                        if(um.count(s[begin]))
                        {
                            --um[s[begin]];
                            // --covered;
                        }
                        ++begin;
                    }
                    
                }
                else
                {
                    ++covered;
                    ++um[s[++end]];
                    while((begin<end)&&((um.count(s[begin]) == 0)||(um[s[begin]]>uTarget[s[begin]])))
                    {
                        // cout<<'!'<<endl;
                        if(um.count(s[begin]))
                        {
                            --um[s[begin]];
                            // --covered;
                        }
                        ++begin;
                    }
                    
                }
            }
            else ++end;
            if(covered>=t.size())
            {
                if(end-begin+1<=minLen)
                {
                    // cout<<"@"<<endl;
                    minBegin = begin;
                    minEnd = end;
                    minLen = end-begin+1;
                }
            }
            // cout<<s.substr(begin, end-begin+1)<<(end-begin+1)<<'|'<<covered<<endl;
        }
        if(covered>=t.size())
        {
            return s.substr(minBegin, minLen);
        }
        else return "";
    }
};

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

使用滑动窗口，假如前面没有重复字符的话就把滑动窗口的后边缘往前移，假如有的话就把前边缘往前移到不重复为止

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()<=1)return s.size();
        unordered_map<char, int> m;
        int maxLen = 0;
        int startInd = 0, endInd = -1;
        while (true)
        {
            while(m.count(s[endInd+1]) == 0||m[s[endInd+1]] == 0)
            {
                ++endInd;
                m[s[endInd]] = 1;
                maxLen = maxLen>=(endInd - startInd+1)?maxLen:(endInd - startInd+1);
                if(endInd == s.size() - 1)
                {
                    return maxLen;
                }
            }

            while(m.count(s[endInd+1])>0&&m[s[endInd+1]]>0)
            {
                
                if(m.count(s[startInd]))
                {
                    m[s[startInd]]-=1;
                    ++startInd;

                }
            }
        }
        return maxLen;
    }
};

双端队列

一种两端都可以进出的数据结构
算法
保持双端队列的头部位置是窗口中最大的数字
窗口的运动是随意的，不是固定窗口大小的
将滑动窗口的右边界向右扩展的时候
双端队列中存储的是双端队列中数字的index，但是使用的是index对应的数字
- 假如此时右边界新进入的数字比此时双端队列的末尾数字大的话就弹出此时双端队列末尾的数字，直到双端队列末尾的数字大于右边界新进入的数字（或者双端队列为空）。严格保证双端队列的单调性。
- 假如此时窗口的左边界向右移动导致窗口内有数字被移出窗口，那么此时将被移出窗口的数字与双端队列头部的数字（也就是此时窗口的最大值）比较，假如二者相同（是同一个index对应的数字），则弹出双端队列头部的数字，否则不管。
- 双端队列的信息实际上是假如此时滑动窗口的右边界不动，但是左边界前移，那么随着前移窗口中的最大值会是谁
- 实际上是用下标大的大数字替换下标小的小数字
  时间复杂度

平均每个时刻都是O(1)

public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    // qmax 窗口最大值的更新结构
    // 放下标
    LinkedList<Integer> qmax = new LinkedList<Integer>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int R = 0; R < arr.length; R++) {
        while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
            qmax.pollLast();
        }
        qmax.addLast(R);
        if (qmax.peekFirst() == R - w) {
            qmax.pollFirst();
        }
        if (R >= w - 1) {
            res[index++] = arr[qmax.peekFirst()];
        }
    }
    return res;
}

leetcode 220. 存在重复元素III

注意需要维护的是一个滑动窗口中的所有元素的排列，要能迅速找到最小值和最大值，同时可以任意删除任何一个元素，使用cpp的有序集合set实现

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        set<int> rec;
        for (int i = 0; i < n; i++) {
            auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);
            if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
                return true;
            }
            rec.insert(nums[i]);
            if (i >= k) {
                rec.erase(nums[i - k]);
            }
        }
        return false;
    }
};

注意有序集合查找最小值和最大值的方法是lower_bound函数
set::lower_bound() 是 C++ STL 中的一个内置函数，用于在集合中查找一个元素。它返回一个迭代器，指向集合中第一个大于等于指定值的元素。如果指定值大于集合中的最大值，则返回指向集合末尾的迭代器。该函数的时间复杂度为 O(logn)，其中 n 是集合的大小。

leetcode 209. 长度最小的子数组

此题因为必须是连续数组，而且是求和，因此考虑使用滑动窗口的方法解决

如果当前窗口内的元素和大于等于目标值，就将开始位置前移，如果不够就将结束位置后移。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int start = 0, end = -1;
        int sum = 0;
        int minLen = INT_MAX;
        do
        {
            // cout<<start<<' '<<end<<endl;
            if(sum<target)
            {
                if(end == nums.size()-1)break;
                ++end;
                sum+=nums[end];
            }
            else 
            {
                if(end-start+1<minLen)
                {
                    minLen = end - start+1;
                }
                sum-=nums[start];
                ++start;
                
            }
        }while(end<nums.size() && end>=start);
        return minLen == INT_MAX?0:minLen;
    }
};

leetcode 76.最小覆盖字串

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

双端队列

算法

时间复杂度

leetcode 220. 存在重复元素III

leetcode 209. 长度最小的子数组