sliding window

sliding window选编

76. Minimum Window Substring

难点：

1. 如何判断window满足要求
2. window满足要求后，如何优化window (start尽可能右移)

目标：

1. 找start
2. 找len

写法一：用HashMap

PS：理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。

public String minWindow(String s, String t) {
    HashMap<Character,Integer> need = new HashMap<>();//用来存储匹配串的字符以及其频率
    HashMap<Character,Integer> window = new HashMap<>();//目前窗口中的字符和其出现的频率
    int t_length = t.length();//匹配串的长度
    /*
     * 统计 匹配串t的字符 和 其出现的频率
     * */
    for (int i = 0; i < t_length; i++) {
        need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1);//获取指定的key对应的 value 如果找不到key 则返回设置的默认值
    }
    int left =0;//初始化左指针
    int right = 0;//初始化右指针

    int valid = 0;//窗口中 满足need条件的字符个数，如果valid和need.size 大小相同 说明 窗口完全满足条件了 可以选择收缩了

    int start = 0;//记录最小覆盖子串的起使索引
    int len = Integer.MAX_VALUE;//记录最小覆盖字串的长度

    //右指针到达 目标串s的末尾的时候停止
    while(right < s.length()){

        char c = s.charAt(right);//获取右指针所在位置的char
        right++;//右指针右移 窗口扩大

        if (need.containsKey(c)){//如果need中包含当前指针所在的字符c
            window.put(c,window.getOrDefault(c,0)+1);//将当前char c 存入对应的window位置
            if (window.get(c).equals(need.get(c))){//如果目标map 中的 相对应的 字符数量符 和 当前window中的 对应的字符数量相同 则 符合的valid++
                valid++;
            }
        }
        while (valid == need.size()){//如果 window中符合need中的char数量则说明确实找到了可行解
            if (right - left < len){//说明现在的子串的长度比 之前记录的长度还要小
                len = right - left;//更新字串长度记录
                start = left;//更新起使索引到left
            }
            //将当前left位置的字符移除窗口
            char d = s.charAt(left);
            //左移窗口
            left++;
            if (need.containsKey(d)){//如果当前移除的字符 存在于 need中 需要对窗口内的数据进行一系列更新
                if (window.get(d).equals(need.get(d))){//如果当前需要移除的字符数量 和 need中需要移除的字符数量相同 则将 匹配的字符个数 -1
                    valid--;
                }
                window.put(d,window.get(d)-1);//将当前的
            }
        }
    }
    //right到达了字符串的末尾
    return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
}

写法二：用数组

to be continued

567. Permutation in String

public boolean checkInclusion(String s1, String s2) {
    Map<Character,Integer> need=new HashMap<>();
    for (int i = 0; i < s1.length(); i++) {
        need.put(s1.charAt(i),need.getOrDefault(s1.charAt(i),0)+1);
    }
    int valid=0;
    int left=0;
    int right=0;
    Map<Character,Integer> window=new HashMap<>();
    while(right<s2.length()){ //[left,right)
        char c=s2.charAt(right);
        window.put(c,window.getOrDefault(c,0)+1);
        right++;
        if(need.containsKey(c)&&need.get(c).equals(window.get(c))){
            valid++;
        }
        while(valid==need.size()){ //找到包含permutation的substring后开始缩，直到满足条件返回true
            if(right-left==s1.length()){
                return true;
            }
            char d=s2.charAt(left);
            left++;
            if(need.containsKey(d)){
                if(need.get(d).equals(window.get(d))){
                    valid--;
                }
                window.put(d,window.get(d)-1);
            }
        }
    }
    return false;
}

3. Longest Substring Without Repeating Characters

sliding window 模板：

现在开始套模板，只需要思考以下四个问题：

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

public int lengthOfLongestSubstring(String s) {
    Map<Character,Integer> map=new HashMap<>();
    int left=0;
    int right=0;
    int max=Integer.MIN_VALUE;
    while(right<s.length()){
        char c=s.charAt(right);
        map.put(c,map.getOrDefault(c,0)+1);
        right++;
        while(map.get(c)!=1){
            char d=s.charAt(left);
            map.put(d,map.get(d)-1);
            left++;
        }
        max=Math.max(max,right-left);
    }
    return max==Integer.MIN_VALUE ? 0 : max;
}

438. Find All Anagrams in a String

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res=new ArrayList<>();
    Map<Character,Integer> need=new HashMap<>();
    Map<Character,Integer> window=new HashMap<>();
    for (int i = 0; i < p.length(); i++) {
        need.put(p.charAt(i),need.getOrDefault(p.charAt(i),0)+1);
    }
    int left=0;
    int right=0;
    int start=0;
    int valid=0;
    while(right<s.length()){ //[left,right)
        char c=s.charAt(right);
        right++;
        if(need.containsKey(c)){
            window.put(c,window.getOrDefault(c,0)+1);
            if(need.get(c).equals(window.get(c))){
                valid++;
            }
        }
        while(valid==need.size()){
            if(right-left==p.length()){//[left,right)
                res.add(left);
            }
            char d=s.charAt(left);
            left++;
            if(window.containsKey(d)){
                window.put(d,window.get(d)-1);
                if(need.get(d)>window.get(d)){
                    valid--;
                }
            }
        }
    }
    return res;
}

159. Longest Substring with At Most Two Distinct Characters

public int lengthOfLongestSubstringTwoDistinct(String s) {
    int n=s.length();
    int res=1;
    int l=0;
    int r=0;
    Map<Character,Integer> map=new HashMap<>();
    while(r<n){
        //[l,r)
        char c=s.charAt(r++);
        map.put(c,map.getOrDefault(c,0)+1);
        while(map.keySet().size()>2){
            c=s.charAt(l++);
            map.put(c,map.get(c)-1);
            if(map.get(c)==0){
                map.remove(c);
            }
        }
        res=Math.max(res,r-l);
    }
    return res;
}

424. Longest Repeating Character Replacement

//longest substring with at most k chars not the same
public int characterReplacement(String s, int k) {
    int n=s.length();
    int[] count=new int[26];
    int left=0;
    int right=0;
    int mostFreqCount=0;
    int res=0;
    while(right<n){
        //[left,right)
        char c=s.charAt(right++);
        count[c-'A']++;
        mostFreqCount=Math.max(mostFreqCount,count[c-'A']);
        while(right-left-mostFreqCount>k){
            char d=s.charAt(left++);
            count[d-'A']--;
        }
        res=Math.max(res,right-left);
    }
    return res;
}

2398. Maximum Number of Robots Within Budget

public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
    int n= chargeTimes.length;
    int left=0;
    int right=0;
    int res=0;
    //[idx,val]
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(b[1]-a[1]));
    long sum=0;
    while(right<n){
        //[left,right)
        sum+=runningCosts[right];
        pq.offer(new int[]{right,chargeTimes[right]});
        right++;
        while(!pq.isEmpty() && pq.peek()[0]<left){
            pq.poll();
        }
        long cur=pq.peek()[1]+(right-left)*sum;
        while(cur>budget){
            sum-=runningCosts[left++];
            while(!pq.isEmpty() && pq.peek()[0]<left){
                pq.poll();
            }
            if(left<right){
                cur=pq.peek()[1]+(right-left)*sum;
            }else{
                cur=0;
            }
        }
        res=Math.max(res,right-left);
    }
    return res;
}

1151. Minimum Swaps to Group All 1’s Together

注意：

• find the subarray of ones length with maximum number of 1

public int minSwaps(int[] data) {
    int ones=0;
    for (int num : data) {
        if(num==1){
            ones++;
        }
    }
    if(ones<=1){
        return 0;
    }
    int n=data.length;
    int max=0;
    int left=0;
    int right=0;
    int count=0;
    while(right<n){
        //[left,right)
        if(data[right++]==1){
            count++;
        }
        if(right-left>ones){
            if(data[left++]==1){
                count--;
            }
        }
        if(right-left==ones){
            max=Math.max(max,count);
        }
    }
    return ones-max;
}

992. Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/523136/JavaC%2B%2BPython-Sliding-Window

public int subarraysWithKDistinct(int[] nums, int k) {
    return atMostK(nums,k)-atMostK(nums,k-1);
}

int atMostK(int[] nums, int k){
    int n=nums.length;
    int res=0;
    Map<Integer,Integer> map=new HashMap<>();
    int l=0;
    for (int r = 0; r < n; r++) {
        if(map.getOrDefault(nums[r],0)==0){
            k--;
        }
        map.put(nums[r],map.getOrDefault(nums[r],0)+1);
        while(k<0){
            map.put(nums[l],map.get(nums[l])-1);
            if(map.get(nums[l])==0){
                k++;
            }
            l++;
        }
        //[l,r] [l+1,r], .. [r,r]
        res+=r-l+1;
    }
    return res;
}

1456. Maximum Number of Vowels in a Substring of Given Length

public int maxVowels(String s, int k) {
    char[] chars=s.toCharArray();
    int n=chars.length;
    int res=0;
    int l=0;
    int r=0;
    int count=0;
    while(r<n){
        //[l,r)
        if(isVowel(chars[r])){
            count++;
        }
        r++;
        if(r-l==k){
            res=Math.max(res,count);
            if(isVowel(chars[l])){
                count--;
            }
            l++;
        }
    }
    return res;
}

private boolean isVowel(char c){
    return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
}

2461. Maximum Sum of Distinct Subarrays With Length K

看到maximum/minimum subarray, 考虑sliding window

public long maximumSubarraySum(int[] nums, int k) {
    int n=nums.length;
    Map<Integer,Integer> window=new HashMap<>();
    int l=0;
    int r=0;
    long max=0;
    long sum=0;
    while(r<n){
        //[l,r)
        sum+=nums[r];
        window.put(nums[r],window.getOrDefault(nums[r],0)+1);
        r++;
        while(r-l>k || window.get(nums[r-1])>1){
            sum-=nums[l];
            window.put(nums[l],window.get(nums[l])-1);
            l++;
        }
        if(r-l==k){
            max=Math.max(max,sum);
        }
    }
    return max;
}

2762. Continuous Subarrays

见Subarray, 思DP or Sliding Window

public long continuousSubarrays(int[] nums) {
    long res=0;
    int l=0;
    int r=0;
    TreeMap<Integer,Integer> map=new TreeMap<>();
    int n=nums.length;
    while(r<n){
        //[l,r)
        map.put(nums[r],map.getOrDefault(nums[r],0)+1);
        r++;
        int max=map.lastKey();
        int min=map.firstKey();
        while(max-nums[r-1]>2 || nums[r-1]-min>2){
            int val=map.get(nums[l]);
            if(val==1){
                map.remove(nums[l]);
            }else{
                map.put(nums[l],val-1);
            }
            l++;
            max=map.lastKey();
            min=map.firstKey();
        }
        //[l,l+1...r-1]
        res+=r-l;
    }
    return res;
}

2747. Count Zero Request Servers

思路：遍历时考察值有进有出，考虑sliding window

vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
     int m = logs.size();
    vector<pair<int,int>> vp;
    for(auto it:logs) vp.push_back({it[1],it[0]}); //time,serverid
    sort(vp.begin(),vp.end()); //sort on basis of time
    
    int q = queries.size();
    unordered_map<int,int> mp;//to store the unique server ids in the current window

    vector<int> ans(q,0);
    vector<pair<int,int>> time(q);
    //store the indices of queries to store the answer in correct manner
    for(int i = 0;i<q;i++) time[i] = {queries[i],i}; //time,index
    sort(time.begin(),time.end()); //sort on basis of time
    
    int i = 0,j = 0; //i is the start of window and j is the end of window
    for(auto tm:time)
    {
        int curtime = tm.first;
        int ind = tm.second;
        
        int start = max(0,curtime-x); //finding the start time (like queries[i]-x), cant be less than 0
        int end = curtime; 
        
        
        while(j<m and vp[j].first<=end) //move j until the value of time in logs is not more than end
        {
            mp[vp[j].second]++; 
            j++;
        }
        while(i<m and vp[i].first<start) //move i until the value is not >= start
        {
            //removing out of window elements
            if(mp[vp[i].second]==1) mp.erase(vp[i].second); //if it is its only occurence then erase it.
            else mp[vp[i].second]--;
            i++;
        }
        ans[ind] = n - mp.size();
    }
    return ans;
}

public int[] countServers(int n, int[][] logs, int x, int[] queries) {
    int len=queries.length;
    int[] res=new int[len];
    Arrays.sort(logs,(a,b)->(a[1]-b[1]));
    int[][] qs=new int[len][2];//idx, queryTime
    for (int i = 0; i < len; i++) {
        qs[i][0]=i;
        qs[i][1]=queries[i];
    }
    Arrays.sort(qs,(a,b)->(a[1]-b[1]));
    Map<Integer,Integer> map=new HashMap<>();//current window
    int l=logs.length;
    int left=0;
    int right=0;//window: [left,right)
    for (int i = 0; i < len; i++) {
        int idx=qs[i][0];
        int t=qs[i][1];
        //consider [t-x,t]
        int start= t-x>=0 ? t-x : 0;
        int end=t;
        while(right<l && logs[right][1]<=end){
            map.put(logs[right][0],map.getOrDefault(logs[right][0],0)+1);
            right++;
        }
        while(left<right && logs[left][1]<start){
            int val=map.get(logs[left][0]);
            if(val==1){
                map.remove(logs[left][0]);
            }else{
                map.put(logs[left][0],val-1);
            }
            left++;
        }
        res[idx]=n-map.size();
    }
    return res;
}