刷题笔记 - 滑动窗口

文章目录

- 滑动窗口
- - 最长无重复子串
  - 最小覆盖子串
  - 串联所有单词的子串
  - 长度最小的子数组
  - 滑动窗口最大值
  - 字符串的排列
  - 最小区间

滑动窗口

所有题目来自leetcode的回答：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai

会员题没有列出来。

最长无重复子串

题目：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, left = 0;
        for (int i = 0; i < n; i ++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            res = Math.max(res, i - left  + 1);
        }
        return res;
    }
}

最小覆盖子串

题目：https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {

    Map<Character, Integer> cnts = new HashMap<>();
    Map<Character, Integer> cntt = new HashMap<>();

    public String minWindow(String s, String t) {
        int ls = s.length(), lt = t.length();
        int milen = Integer.MAX_VALUE, st = 0,  ed = 0, mist = 0, mied = 0;
        boolean isNull = false;
        for (int i = 0 ; i < lt; i ++) {
            cntt.put(t.charAt(i), cntt.getOrDefault(t.charAt(i), 0) + 1);
        }
        while (ed < ls) {
            if (cntt.containsKey(s.charAt(ed))) {
                cnts.put(s.charAt(ed), cnts.getOrDefault(s.charAt(ed), 0) + 1);
                while (check()) {  // 这里是while，一步更新到第二个在cntt里的字符，过滤掉无用字符
                    isNull = true;
                    if (milen > ed - st + 1) {
                        milen = ed - st + 1;
                        mist = st;
                        mied = ed;
                    }
                    if (cntt.containsKey(s.charAt(st))) {
                        cnts.put(s.charAt(st), cnts.getOrDefault(s.charAt(st), 0) - 1);
                    }
                    st ++;
                }
            }
            ed ++;
        }
        if (!isNull) return "";
        return s.substring(mist, mied + 1);
    }

    private boolean check() {
        Iterator iter = cntt.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnts.getOrDefault(key, 0) < val) return false;
        }
        return true;
    }
}

串联所有单词的子串

题目：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

题解：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solutions/3825/chuan-lian-suo-you-dan-ci-de-zi-chuan-by-powcai

// 对words中的所有单词，维护一个单词计数map
// 串联子串中保证了每个子单词的原字符顺序不变
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int ls = s.length(), n = words.length;
        int lw = n * words[0].length(), oneLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        if (lw > ls) return res;
        Map<String, Integer> wordsMap = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < ls - lw + 1; i ++) {  //  i < ls - lw + 1，保证能枚举到最后一个窗口的第一个下标位置
            Map<String, Integer> tmpMap = new HashMap<>();
            for (int j = i; j < i + lw; j += oneLen) {
                String subStr = s.substring(j, j + oneLen);
                tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);
            }
            if (wordsMap.equals(tmpMap)) res.add(i);
        }
        return res; 
    }
}

优化：（常规的滑动窗口思路，和最小覆盖子串的代码逻辑相似）

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int ls = s.length(), n = words.length;
        int lw = n * words[0].length(), oneLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        if (lw > ls) return res;
        Map<String, Integer> wordsMap = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < oneLen; i ++) {  // 保证枚举到所有单词[0...oneLen], [1...oneLen + 1], ...
            int st = i, ed = i, cnt = 0;
            Map<String, Integer> tmpMap = new HashMap<>();
            while (ed < ls - oneLen + 1) {  // 同解法一的判断
                String subStr = s.substring(ed, ed + oneLen);
                tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);
                ed += oneLen;
                cnt ++;  // 当前窗口里有几个单词
                while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {
                    // 窗口里的单词并不在wordsMap里，移动窗口
                    // 或者，窗口里当前单词重复出现了，移动窗口
                    String stStr = s.substring(st, st + oneLen);  // 窗口里最左边的单词
                    tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);
                    st += oneLen;
                    cnt --;
                }
                if (cnt == n) res.add(st);
            }
        }
        return res;
    }
}

再优化（直接跳过不在words里的单词和窗口）：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int ls = s.length(), n = words.length;
        int lw = n * words[0].length(), oneLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        if (lw > ls) return res;
        Map<String, Integer> wordsMap = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < oneLen; i ++) {  // 保证枚举到所有单词[0...oneLen], [1...oneLen + 1], ...
            int st = i, ed = i, cnt = 0;
            Map<String, Integer> tmpMap = new HashMap<>();
            while (ed < ls - oneLen + 1) {  // 同解法一的判断
                String subStr = s.substring(ed, ed + oneLen);
                ed += oneLen;
                if (!wordsMap.containsKey(subStr)) {
                    /**
                        当前窗口的当前单词不是words里的单词，肯定不符合题意，更新窗口。
                        题中要求所有串联单词必须挨在一起，这个判断过滤掉不挨在一起的窗口
                     */
                    cnt = 0;
                    st = ed;
                    tmpMap.clear();
                    continue;
                }
                tmpMap.put(subStr, tmpMap.getOrDefault(subStr, 0) + 1);
                cnt ++;  // 当前窗口里有几个单词
                while(tmpMap.getOrDefault(subStr, 0) > wordsMap.getOrDefault(subStr, 0)) {
                    // 窗口里的单词并不在wordsMap里，移动窗口
                    // 或者，窗口里当前单词重复出现了，移动窗口
                    String stStr = s.substring(st, st + oneLen);  // 窗口里最左边的单词
                    tmpMap.put(stStr, tmpMap.getOrDefault(stStr, 0) - 1);
                    st += oneLen;
                    cnt --;
                }
                if (cnt == n) res.add(st);
            }
        }
        return res;
    }
}

长度最小的子数组

题目：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int milen = Integer.MAX_VALUE, st = 0, ed = 0, sum = 0;
        boolean isNull = false;
        while (ed < n) {
            sum += nums[ed];
            while (sum >= target) {
                isNull = true;
                if (milen > ed - st + 1) {
                    milen = ed - st + 1;
                }
                sum -= nums[st];
                st ++;
            }
            ed ++;
        }
        if (!isNull) return 0;
        return milen;
    }
}

滑动窗口最大值

题目：https://leetcode.cn/problems/sliding-window-maximum/description/

题解：https://leetcode.cn/problems/sliding-window-maximum/solutions/2361228/239-hua-dong-chuang-kou-zui-da-zhi-dan-d-u6h0

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 借鉴最小栈的思路，再O(1)时间内找出窗口内的最大值
        // 双向队列维持一个窗口内的非严格递减排序
        // 队头是窗口内的最大值
        int n = nums.length;
        if (k == 1) return nums;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new LinkedList<>();
        int idx = 0;
        for (int i = 0; i < k; i ++) {
            while (!dq.isEmpty() && dq.peekLast() < nums[i]) {
                dq.removeLast();
            }
            dq.addLast(nums[i]);
        }
        res[idx ++] = dq.peekFirst();
        for (int i = k; i < n; i ++) {
            if (dq.peekFirst() == nums[i - k]) dq.removeFirst();
            while (!dq.isEmpty() && dq.peekLast() < nums[i]) {
                dq.removeLast();
            }
            dq.addLast(nums[i]);
            res[idx ++] = dq.peekFirst();
        }
        return res;
    }
}

字符串的排列

题目：https://leetcode.cn/problems/permutation-in-string/description/

题解-方法二：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/solutions/355881/zui-xiao-qu-jian-by-leetcode-solution

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int ls1 = s1.length(), ls2 = s2.length();
        if (ls1 > ls2) return false;
        int[] cnt1 = new int[26], cnt2 = new int[26];
        for (int i = 0; i < ls1; i ++) {
            cnt1[s1.charAt(i) - 'a'] ++;
            cnt2[s2.charAt(i) - 'a'] ++;
        }
        if (Arrays.equals(cnt1, cnt2)) return true;
        for (int i = ls1; i < ls2; i ++) {
            cnt2[s2.charAt(i - ls1) - 'a'] --;
            cnt2[s2.charAt(i) - 'a'] ++;
            if (Arrays.equals(cnt1, cnt2)) return true;
        }
        return false;
    }
}

最小区间

题目：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/description/

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int n = nums.size();
        Map<Integer, List<Integer>> index = new HashMap<>();
        int mi = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
        for (int i = 0; i < n; i ++) {
            for (int item : nums.get(i)) {
                List<Integer> tmp = index.getOrDefault(item, new ArrayList<Integer>());
                tmp.add(i);
                index.put(item, tmp);
                if (mi > item) mi = item;
                if (mx < item) mx = item;
            }
        }
        int st = mi, ed = mi - 1, ansSt = 0, ansEd = Integer.MAX_VALUE, cnt = 0;
        // System.out.println(mi + ", " + mx);
        int[] interval = new int[n];   // 记录滑动窗口覆盖了多少区间,下标标识某个区间
        while (ed < mx) {
            ed ++;
            if (index.containsKey(ed)) {
                for (int idx : index.get(ed)) {  // 枚举被覆盖的区间
                    interval[idx] ++;
                    if (interval[idx] == 1) {  // idx标识的区间第一次被覆盖时，标记该区间被覆盖
                        cnt ++;
                    }
                    while (cnt == n) {  // 当所有区间被覆盖，更新最小区间和窗口
                        if (ed - st < ansEd - ansSt) {
                            // System.out.println("*--*-*-");
                            ansSt = st;
                            ansEd = ed;
                        }
                        if (index.containsKey(st)) {  // 更新最小区间的左端点，看是否能覆盖全部区间
                            for (int leftIdx : index.get(st)) {
                                interval[leftIdx] --;
                                if (interval[leftIdx] == 0) {
                                    cnt --;
                                }
                            }
                        }
                        st ++;
                    }
                }
            }
        }
        return new int[] {ansSt, ansEd};
    }
}