关于数据结构:20211219刷题笔记滑动窗口系列

窗口的思路是存在一个窗口。满足条件，这时候扭转窗口的大小，到不满足条件时，挪动窗口的右边界线

int[] check = new int[size];
// 左边界
int left =0;
// 右边界
int right = 1;
// 这个时候就曾经初步创立了窗口
freq[in.0] = init;
// 当初开始滑动窗口
ans = init;
while(right<in.len){
    // 当窗口不非法
    while(check[in.right] is not valid){
        // 挪动窗口使窗口非法
        check[in.(left++)] = !init;
    }
    // 这个时候窗口非法
    check[in.right] = init;
    ans = better(ans,right-left+1);
    right++;
}
rerurn ans;

套用公式
3. 无反复字符的最长子串

滑动窗口一道很典型的题。

int[] check = new int[127];
// 左边界
int left =0;
// 右边界
int right = 1;
// 这个时候就曾经初步创立了窗口
freq[s.charAt(0)] = 1;
// 当初开始滑动窗口
ans = 1;
while(right<in.length()){
    // 当窗口不非法
    while(check[in.s.charAt(right)] >0){
        // 挪动窗口使窗口非法
        check[s.charAt(left++)]--;
    }
    // 这个时候窗口非法
    check[in.s.charAt(right)]++;
    ans = Math,max(ans,right-left+1);
    right++;
}
rerurn ans;

再用公式套用一个比较复杂的题目
30. 串联所有单词的子串

// 窗口大小
HashSet<String> validSet ;
    HashSet<String> inValidSet ;
    public List<Integer> findSubstring(String s, String[] words) {int size = words.length * words[0].length();
        int left = 0;
        int right = size - 1;
        List<Integer> list = new ArrayList<>();
        validSet = new HashSet<>();
        inValidSet = new HashSet<>();
        while (right < s.length()) {while (right<s.length() && !isValid(s, left, right,words)) {
                left++;
                right++;
            }
            if (right<s.length()){list.add(left);
                left++;
                right++;
            }

        }
        return list;
    }
    private boolean isValid(String s,int left,int right,String[] words) {if (validSet.contains(s.substring(left,right+1))) return true;
        if (inValidSet.contains(s.substring(left,right+1))) return false;

        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {map.put(word, map.getOrDefault(word, 0) + 1);
        }
        while (left <= right) {String temp = s.substring(left, left + words[0].length());
            Integer freq = map.getOrDefault(temp, 0);
            if (freq > 0) map.put(temp, freq - 1);
            else {inValidSet.add(s);
                return false;
            }
            left += words[0].length();}
        validSet.add(s);
        return true;
    }

再比方，咱们再套一道题
187. 反复的 DNA 序列
这个题目稍为简略

class Solution {public List<String> findRepeatedDnaSequences(String s) {
        int left = 0;
        int right = 10;
        ArrayList<String> resp = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        while (right<=s.length()){String temp = s.substring(left, right);
            map.put(temp,map.getOrDefault(temp,0)+1);
            right++;
            left++;
        }
        for (String k : map.keySet()) {if (map.get(k) > 1) {resp.add(k);
            }
        }
        return resp;

    }
}