labuladong commented 1 year ago

本期打卡已结算完成。报名最新一期的打卡活动点这里

ImmersiveAngela commented 1 year ago

无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/2376196/3-wu-zhong-fu-zi-fu-de-zui-chang-zi-chua-c4ap/

macksonyli21826 commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2376270/problem-76-zui-xiao-fu-gai-zi-chuan-by-h-viog/

ElaineZhou-moon commented 1 year ago

https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/3873900/3-longest-substring-without-repeating-characters/

zexianw12 commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2376293/hua-dong-chuang-kou-fa-jie-jue-zhao-zui-eokk6/

GodisinHisHeaven commented 1 year ago

https://leetcode.com/problems/minimum-window-substring/solutions/3874066/sliding-window-python-solution/

Reset0808 commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2376375/hua-dong-chuang-kou-by-2ba4zmutle-ga8r/

chen-huanxin commented 1 year ago

76：https://leetcode.cn/problems/minimum-window-substring/solutions/2376442/cpphua-dong-chuang-kou-0807-76-zui-xiao-bpq5f/

Chao200 commented 1 year ago

3： https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/2376433/solution3-wu-zhong-fu-zi-fu-de-zui-chang-wqbx/

438： https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/2376487/solution438-zhao-dao-zi-fu-chuan-zhong-s-xsjz/

567： https://leetcode.cn/problems/permutation-in-string/solutions/2376493/solution567-zi-fu-chuan-de-pai-lie-by-xi-vdvy/

76： https://leetcode.cn/problems/minimum-window-substring/solutions/2376520/solution76-zui-xiao-fu-gai-zi-chuan-by-x-evew/

javaSnacks commented 1 year ago

3: https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/2376584/3-wu-zhong-fu-zi-fu-de-zui-chang-zi-chua-6e2t/

dh0072 commented 1 year ago

Q76. Minimum Window Substring https://leetcode.com/problems/minimum-window-substring/discuss/3874842/Java-sliding-window-solution

ConnieLuksc commented 1 year ago

https://leetcode.com/problems/longest-substring-without-repeating-characters/solutions/3875115/using-sliding-window-to-solve-longest-substing/

Sadwy commented 1 year ago

LC438. https://leetcode.com/problems/find-all-anagrams-in-a-string/solutions/3875304/standard-sliding-window/

guabigwind commented 1 year ago

最小覆盖子串： https://leetcode.cn/problems/minimum-window-substring/solutions/2376961/zui-xiao-fu-gai-zi-chuan-by-guabigwind-arip/

guabigwind commented 1 year ago

最小覆盖子串： https://leetcode.cn/problems/minimum-window-substring/solutions/2376961/zui-xiao-fu-gai-zi-chuan-by-guabigwind-arip/

ghost commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2377133/hua-dong-chuang-kou-zui-xiao-fu-gai-zi-c-sg1r/

Xiaolin8991 commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2377224/python3-hua-dong-chuang-kou-wen-ti-by-xi-j76q/

Jingzhenzxz commented 1 year ago

https://leetcode.cn/problems/minimum-window-substring/solutions/2377303/hua-dong-chuang-kou-wen-ti-yao-zhu-yi-sa-7j1v/

Problem: 76. 最小覆盖子串

[TOC]

思路

滑动窗口：先找出所有的合规情况，然后从这些情况中找出答案，例如取最值。也就是说，窗口里的数据就是合规的数据，也就是说，直到找到合规的情况，左指针才右移。

滑动窗口问题要注意三点：

窗口里存的是什么，这直接决定什么时候右移右边界，什么时候右移左边界。
操作之前要保存数据，操作完要更新数据。
操作或更新数据时要利用滑动窗口的差集性。比如新建一个集合或数组，然后利用差集性更新集合或数组中的数据。即利用空间换时间。差集性就是前后操作之间的信息有联系，信息可以复用，比如信息是递推的，我们一定要利用这种联系，不要孤零零地用个contains查询完当前字符是否是目标字符就完事了，这是一次性的，这样查询完没有留下任何痕迹或贡献。

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

Code


class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0;
        int len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 一定不要用 ==！要用 equals！
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left + 1 < len) {
                    start = left;
                    len = right - left + 1;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    // 一定不要用 ==！要用 equals！
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len - 1);
    }
}