网站微信认证费用多少钱,可以营销的十大产品,wordpress plugin开发,网页浏览历史记录恢复子串基础 前缀和#xff1a;前面的数加在一起等于多少#xff0c;放进map里#xff0c;key为和#xff0c;value为这个和出现的次数。单调队列#xff1a;单调递增/递减队列#xff0c;每次加入新元素#xff0c;比新元素大/小的元素全部弹出。滑动窗口#xff1a;两层… 子串基础 前缀和前面的数加在一起等于多少放进map里key为和value为这个和出现的次数。单调队列单调递增/递减队列每次加入新元素比新元素大/小的元素全部弹出。滑动窗口两层循环外层循环扩展右边界内层循环缩减左边界。 560. 和为 K 的子数组 题目讲解LeetCode 重点 利用当前和减去k等于前缀和这个条件来快速判断。 思路 preSumMap存储前缀和出现的次数。如果当前和减去k出现在preSumMap前缀和字典中说明当前子数组满足条件。 复杂度 n 是数组长度时间复杂度O(n)空间复杂度O(n) public int subarraySum(int[] nums, int k) {int result 0;// 重点: 用一个map来记录该和出现的次数MapInteger, Integer preSumMap new HashMap();preSumMap.put(0, 1);int curSum 0;for (int i 0; i nums.length; i) {curSum nums[i];// 重点: 如果 当前和减去k 所需要的前缀和存在则找到答案if (preSumMap.containsKey(curSum - k)) {result preSumMap.get(curSum - k);}preSumMap.put(curSum, preSumMap.getOrDefault(curSum, 0) 1);}return result;
}239. 滑动窗口最大值 题目讲解LeetCode 重点 队尾只要有更年轻i越靠后同时还能力更强数值越大的留着其他比它更早入职同时能力却更差的没有什么意义统统开了队首的虽然能力最强但是年龄最大一旦发现它超过年龄范围不在滑动窗口的范围内不用看能力就可以直接开了。 思路 定义一个单调递减队列。前k个单独处理然后从index为k的开始遍历利用单调递减队列来快速获取当前窗口最大值。单调递减队列的pop需要处理过期元素。 复杂度 n 是数组长度时间复杂度O(n)。遍历一遍nums空间复杂度O(k)。队列最多塞k个元素 class MonotonicQueue {DequeInteger monotonicQueue;public MonotonicQueue() {this.monotonicQueue new LinkedList();}public int getMaxValues() {return monotonicQueue.getFirst();}public void pop(int val) {// 检查队列头元素是否为上一个窗口头元素, 如果是弹出, 因为已经过期了if (monotonicQueue.getFirst() val) monotonicQueue.pollFirst();}public void push(int val) {// 推入新元素, 比新元素小的全部popwhile (!monotonicQueue.isEmpty() val monotonicQueue.peekLast()) {monotonicQueue.pollLast();}monotonicQueue.offer(val);}
}public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length 1) return nums;MonotonicQueue monotonicQueue new MonotonicQueue();int[] result new int[nums.length - k 1];int resultIndex 0;// 前k个单独处理for (int i 0; i k; i) {monotonicQueue.push(nums[i]);}result[resultIndex] monotonicQueue.getMaxValues();resultIndex;// 重点: 利用单调递减队列快速获取当前窗口最大值for (int i k; i nums.length; i) {monotonicQueue.pop(nums[i - k]);monotonicQueue.push(nums[i]);result[resultIndex] monotonicQueue.getMaxValues();resultIndex;}return result;
}76. 最小覆盖子串 题目讲解LeetCode 重点 滑动窗口外层循环控制右边界内层循环控制左边界。利用当前匹配好的字符数量来缩减左边界。 思路 滑动窗口。外层循环扩展右边界内层循环缩减左边界。用matchedChars来记录当前匹配好的字符数量。如果matchedChars跟字符串t的长度相同说明当前滑动窗口子串满足条件开始缩减左边界。如果左边界缩过头就返回到外层循环继续拓展右边界了。 复杂度 n 是字符串s的长度时间复杂度O(n)空间复杂度O(1) public String minWindow(String s, String t) {if (s.equals(t)) return s;if (t.length() s.length()) return ;int[] tCount new int[128];for (char c : t.toCharArray()) tCount[c];int[] curCount new int[128];int left 0, right 0;int min Integer.MAX_VALUE;int matchedChars 0;int start 0;// 重点: 外层循环不断扩展右边界while (right s.length()) {char rightChar s.charAt(right);// 当前右边界的字符出现在字符串t中if (tCount[rightChar] 0) {// 更新匹配好的字符数量if (curCount[rightChar] tCount[rightChar]) matchedChars;curCount[rightChar];}// 重点: 内层for循环缩减左边界// 如果匹配好的字符数量跟字符串t的长度相同了while (matchedChars t.length()) {if (right - left min) {min right - left 1;start left;}char leftChar s.charAt(left);if (tCount[leftChar] 0) {// 如果减去当前left的字符会不满足字符串t, 那么更新matchedChars来跳出循环if (curCount[leftChar] tCount[leftChar]) matchedChars--;curCount[leftChar]--;}left;}right;}if (min Integer.MAX_VALUE) return ;return s.substring(start, start min);
}
