《LeetCode热题100》---＜4.子串篇三道＞

用户11288958

发布于 2024-09-24 15:19:12

860

发布于 2024-09-24 15:19:12

文章被收录于专栏：用户11288958的专栏

本篇博客讲解LeetCode热题100道子串篇中的三道题第一道：和为 K 的子数组第二道：滑动窗口最大值第三道：最小覆盖子串

第一道：和为 K 的子数组（中等）

法一：暴力枚举

 class Solution {
    public int subarraySum(int[] nums, int target) {
        int count = 0;
        for (int start = 0; start < nums.length; ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == target) {
                    count++;
                }
            }
        }
        return count;
    }
}

思想比较简单，找到所有子数组的和，如果等于目标值target。那么count++ 最终返回count

法二：前缀和 + 哈希表优化

class Solution {
    public int subarraySum(int[] nums, int target) {
        int count = 0, pre = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - target)) {
                count += map.get(pre - target);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

前缀和：是求解子数组的和等问题的好方法。通过累加数组中的值，使其减去数组中某个值来得到子数组的和。

前缀和用法示例:

建哈希表优化后。

前缀和： 使用pre += nums[i]; 用pre变量来累加前缀和。只需要pre即可。因为我们只需要用累加和减去目标值target。再去哈希表中找有没有对应的值。如果有对应的值，说明存在子数组的和为target。那么count++ 最终返回conunt

第二道：滑动窗口最大值（困难）

法一：优先队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pQueue.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pQueue.peek()[0];
        for (int i = k; i < n; ++i) {
            pQueue.offer(new int[]{nums[i], i});
            while (pQueue.peek()[1] <= i - k) {
                pQueue.poll();
            }
            ans[i - k + 1] = pQueue.peek()[0];
        }
        return ans;
    }
}

定义一个优先队列（最大堆）pQueue，用于存储滑动窗口内的元素。队列按照元素值降序排列，如果值相同则按索引降序排列。
初始化队列，将数组前 k 个元素加入队列。
创建结果数组 ans，用于存储每个窗口的最大值。
将队列顶部（最大值）的元素值存入结果数组的第一个位置。
从第 k 个元素开始，逐步将元素加入队列，并移除不在当前滑动窗口内的元素（根据索引判断）。
每次移动窗口后，将当前窗口的最大值（队列顶部元素值）存入结果数组相应位置。
最终返回结果数组。

使用优先队列高效地计算了数组中每个滑动窗口的最大值。

法二：单调队列（单调性的双端队列）

单调队列套路

入（元素进入队尾，同时维护队列单调性）
出（元素离开队首）
记录/维护答案（根据队首）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

初始化一个双端队列，用于存储数组元素的索引。
遍历数组前 k 个元素，保持队列中元素对应的数组值按降序排列，并存储这些元素的索引。
初始化结果数组 ans 并将第一个窗口的最大值（队列头部的元素）存入 ans 的第一个位置。
遍历数组剩余元素：

将新的元素索引加入队列，并移除队列中所有比当前元素小的元素的索引。
移除队列中不在当前窗口范围内的索引。
将当前窗口的最大值（队列头部的元素）存入 ans 的相应位置。

最终返回结果数组 ans。

法三：分块 + 预处理

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }
            else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}

初始化前缀最大值和后缀最大值数组：
- prefixMax[i] 表示从块的开始到索引 i 的最大值。
- suffixMax[i] 表示从索引 i 到块的结束的最大值。
构建前缀最大值数组：
- 遍历数组，如果索引 i 是块的开始，prefixMax[i] 等于 nums[i]。
- 否则，prefixMax[i] 等于 prefixMax[i - 1] 和 nums[i] 的最大值。
构建后缀最大值数组：
- 从数组末尾遍历，如果索引 i 是块的结束，suffixMax[i] 等于 nums[i]。
- 否则，suffixMax[i] 等于 suffixMax[i + 1] 和 nums[i] 的最大值。
计算每个滑动窗口的最大值：
- 遍历 ans 数组，每个窗口的最大值是 suffixMax[i] 和 prefixMax[i + k - 1] 的最大值。
返回结果数组：
- 返回存有每个滑动窗口最大值的结果数组 ans

第三道：最小覆盖子串（困难）

方法一：滑动窗口

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

    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.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 (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

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

初始化哈希表：
- 使用 ori 哈希表记录字符串 t 中每个字符出现的次数。
- 使用 cnt 哈希表记录当前窗口中每个字符的出现次数。
滑动窗口的初始化：
- 初始化左指针 l 和右指针 r，分别表示当前窗口的左右边界。
- 初始化记录最小窗口长度的 len 和最小窗口的起始和结束位置 ansL 和 ansR。
滑动窗口扩展：
- 移动右指针扩展窗口，若当前字符在 t 中，将其加入 cnt。
缩小窗口：
- 当窗口内包含了 t 中所有字符时，尝试缩小窗口：
  - 如果当前窗口长度小于已记录的最小窗口长度，更新最小窗口的位置和长度。
  - 移动左指针，若左指针指向的字符在 t 中，将其从 cnt 中移除。
返回结果：
- 如果找到了符合条件的窗口，返回最小窗口的子字符串，否则返回空字符串。
辅助方法 check：
- 检查当前窗口是否包含 t 中所有字符，即 cnt 中每个字符的数量是否都不小于 ori 中对应的数量。