刷题日记 24.4.2

滑动窗口专题，今天三道滑动窗口的题目

lc209. 长度最小的子数组（MD）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

我们先不看进阶要求，进阶的稍后我会讲讲我的思路……

这道题是一道非常经典的滑动窗口题目。滑动窗口是什么东西？这个东西应该来源于计算机网络，TCP用于控制流量的一个措施之一，现在我们把滑动窗口这个模型拿出来用在算法题上面，也是一个非常好用的算法解题技巧

其实滑动窗口的本质，还是昨天讲过的双指针。滑动窗口的左右两端由两个指针 l 和 r 进行控制移动，这不就是双指针模型了吗，处理滑动窗口的思路和双指针的思路基本上是接近的，只要双指针学明白了，滑动窗口也不难理解

这道题不难，直接给题解代码，用双指针的思路来看这道题还是很容易理解的

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0, sum = 0;
        int res = Integer.MAX_VALUE;
        while (r < nums.length) {
            sum += nums[r];
            while (sum >= target) {
                res = Math.min(res, r - l + 1);
                sum -= nums[l++];
            }
            r++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

然后简单讲讲进阶要求。进阶要求我们使用 O(nlog(n)) 的时间复杂度来完成本题……我能想到的方法就是先去排序，然后处理思路和昨天做过的三数之和差不多，这样就能达到 O(nlog(n)) 的时间复杂度。不过我没有自己动手写过，有时间可以写一下

lc3. 无重复字符的最长子串（MD）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

这道题还是滑动窗口，前面说到了，滑动窗口的本质其实就是同向移动的双指针

关于 不包含重复字符 ，当然要用 HashSet 来去重，不用多说了

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> hash = new HashSet<>();
        int r = -1, ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i != 0) {
                hash.remove(s.charAt(i - 1));
            }
            while (r + 1 < s.length() && !hash.contains(s.charAt(r + 1))) {
                hash.add(s.charAt(r + 1));
                r++;
            }
            ans = Math.max(ans, r - i + 1);
        }
        return ans;
    }
}

lc76. 最小覆盖子串（HD）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

本栏目开设以来接触的第……三道hard题吧？

这道题倒是有点hard的样子了，当然这道题其实还是和刚刚的 lc3 一样，双指针+哈希表去重。与 lc3 不一样的是，这道题要先预处理，然后需要做特判

class Solution {
    Map<Character, Integer> hash = new HashMap<>();
    Map<Character, Integer> cnt = new HashMap<>();

    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        for (int i = 0; i < t.length(); i++) {
            cnt.put(t.charAt(i), cnt.getOrDefault(t.charAt(i), 0) + 1);
        }
        int l = 0, r = -1;
        int ansL = -1, ansR = -1;
        int len = Integer.MAX_VALUE;
        while (r < s.length()) {
            r++;
            if (r < s.length() && cnt.containsKey(s.charAt(r))) {
                hash.put(s.charAt(r), hash.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (cnt.containsKey(s.charAt(l))) {
                    hash.put(s.charAt(l), hash.getOrDefault(s.charAt(l), 0) - 1);
                }
                l++;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

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

从代码量就能看出，这不是一个轻松的hard题，尤其是初见，如果不通过debug直接一次性a出来其实是有点小难的。个人认为这道题应该属于中位hard，之前提到的两道hard题都属于下位hard

lc141. 环形链表（EZ）

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

hard题结束了，我们来道简单题，环形链表判断

又是快慢双指针，不知道大家有没有腻味，反正我已经做这种题已经做腻了

简单题，不讲解。直接给代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}