php快速建站工具,东莞网站建设营销哪家好,网站系统定制,网络推广专员岗位职责本篇博客讲解LeetCode热题100道子串篇中的三道题 第一道#xff1a;和为 K 的子数组 第二道#xff1a;滑动窗口最大值 第三道#xff1a;最小覆盖子串 第一道#xff1a;和为 K 的子数组#xff08;中等#xff09; 法一#xff1a;暴力枚举 class Solution {public in… 本篇博客讲解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;PriorityQueueint[] pQueue new PriorityQueueint[](new Comparatorint[]() {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;DequeInteger deque new LinkedListInteger();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 {MapCharacter, Integer ori new HashMapCharacter, Integer();MapCharacter, Integer cnt new HashMapCharacter, 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 中对应的数量。
