leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">和为 K 的子数组(mid)
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
输入:nums = [1,1,1], k = 2
输出:2
解法1:前缀和+Map
这是一道经典的前缀和运用题。
统计以每一个 nums[i] 为结尾,和为 k 的子数组数量即是答案。
我们可以预处理前缀和数组 prefix,对于求解以某一个 nums[i] 为结尾的,和为 k 的子数组数量,本质上是求解在 [0,i] 中,prefix 数组中有多少个值为 prefix[i]−k 的数,这可以在遍历过程中使用「哈希表」进行同步记录。
是以当前节点为结尾的计算,不是以当前节点为起始的计算!!!
public int subarraySum(int[] nums, int k) {int len = nums.length;int[] prefix = new int[len];prefix[0] = nums[0];for (int i=1; i<len; i++){prefix[i] = prefix[i-1]+nums[i];}Map<Integer,Integer> map = new HashMap<>();//当子串的起始节点为0,即取前缀和的整段而不做截断//需要插入一个长度为0的子串map.put(0,1);int res = 0;for(int i=0; i<len; i++){res += map.getOrDefault(prefix[i]-k,0);map.put(prefix[i],map.getOrDefault(prefix[i],0)+1);}return res;
}
leetcode.cn/problems/sliding-window-maximum/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">滑动窗口最大值(hard)
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
解法1:滑动窗口,最优
假设我们当前处理到某个长度为 k 的窗口,此时窗口往后滑动一格,会导致后一个数(新窗口的右端点)添加进来,同时会导致前一个数(旧窗口的左端点)移出窗口。
随着窗口的不断平移,该过程会一直发生。若同一时刻存在两个数 nums[j] 和 nums[i](j<i)所在一个窗口内,下标更大的数会被更晚移出窗口,此时如果有 nums[j]<=nums[i] 的话,可以完全确定 nums[j] 将不会成为后续任何一个窗口的最大值,此时可以将必然不会是答案的 nums[j] 从候选中进行移除。
不难发现,当我们将所有必然不可能作为答案的元素(即所有满足的小于等于 nums[i] )移除后,候选集合满足「单调递减」特性,即集合首位元素为当前窗口中的最大值(为了满足窗口长度为 k 的要求,在从集合头部取答案时需要先将下标小于的等于的 i−k 的元素移除)。
为方便从尾部添加元素,从头部获取答案,我们可使用「双端队列」存储所有候选元素。
用一个容器,充当窗口,保持它存储的元素是单调非递增,这样它的第一个元素就是容器中的最大值,最后一个就是最小值,根据前面的分析,向右滑动过程中,如果遇到了更大的元素,就可以把在容器中小于它的元素都移除掉,因为后加入的更大的元素才可能成为容器中的最大值。因为第一个元素是最大值,我们需要能够获取它,所以,这是一个先入先出的容器,这里用队列就可以了。它的思路与单调栈一样,但只不过用队列来当容器,这便是“单调队列”了。
public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> stack = new ArrayDeque<>();int[] res = new int[nums.length-k+1];for(int i=0; i<nums.length; i++){// 队列中的下标是小于新加入的i,那么如果[i]>= 队尾// 说明队尾肯定不会是窗口里的一个最大值了// 从队尾开始,把小于[i]的都移除掉。// 这样就能保证队列的值是一个单调非递减队列了while(!stack.isEmpty() && nums[stack.peekLast()]<nums[i]){stack.pollLast();}stack.addLast(i);if(i>=k-1){// 现在的队首就是窗口中的最大值res[i-k+1] = nums[stack.peekFirst()];// 再把左滑出窗口的最大值从队列中移除,因为它已被滑出窗口了if(stack.peekFirst()+k-1 == i) stack.pollFirst();}}return res;
}
解法2:优先队列
public int[] maxSlidingWindow(int[] nums, int k) {// 使用优先队列(大顶堆)来存储窗口中的索引,以便快速找到最大值PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[b] - nums[a]);// 初始化结果数组,长度为 nums 数组长度减去窗口大小 k 再加 1int[] res = new int[nums.length - k + 1];for (int i = 0; i < nums.length; i++) {// 将当前索引 i 加入优先队列pq.add(i);// 当索引 i 大于 k-1 时,说明窗口已经滑动了至少 k 次,可以开始记录最大值if (i >= k - 1) {// 记录窗口内的最大值,即优先队列中索引对应的值res[i - k + 1] = nums[pq.peek()];// 清除出窗口的元素,即索引小于 i-k+1 的元素while (!pq.isEmpty() && pq.peek() <= i - k + 1) {pq.poll();}}}// 返回结果数组,包含了每个窗口的最大值return res;
}
leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked" rel="nofollow">最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
解法1:滑动窗口
public String minWindow(String s, String t) {// 初始化一个足够大的数组来计数字符,假设字符集大小为70(A-Z的大小写)int[] cnt = new int[70];// 标记是否找到有效子串boolean flag = false;// 遍历字符串 t,对每个字符进行计数,并将对应的数组元素减1for (int i = 0; i < t.length(); i++) {char c = t.charAt(i);cnt[c - 'A']--; // 将字符转换为0-65的整数,便于在数组中索引}// 初始化结果字符串为 s,假设没有找到更小的子串String res = s;// 初始化左右指针int l = 0, r = 0;// 滑动窗口的右边界while (r < s.length()) {// 将 s 的当前字符计数加1cnt[s.charAt(r) - 'A']++;// 当前窗口包含 t 的所有字符时,尝试收缩左边界while (l <= r && check(cnt)) {// 标记已找到有效子串flag = true;// 更新最小窗口String tmp = s.substring(l, r + 1);res = tmp.length() < res.length() ? tmp : res;// 移动左边界,将 l 所指的字符从计数器中减去cnt[s.charAt(l) - 'A']--;l++;}// 扩展右边界,继续寻找可能的最小子串r++;}// 如果找到了有效子串,返回 res,否则返回空字符串return flag ? res : "";
}// 检查数组中的所有计数是否都大于等于0,即 s 的当前窗口是否包含 t 的所有字符
public boolean check(int[] arr) {for (int i = 0; i < arr.length; i++) {if (arr[i] < 0)return false; // 如果有字符计数小于0,则当前窗口不包含 t 的所有字符}return true; // 所有字符计数都非负,说明当前窗口包含 t 的所有字符
}
定义两个长度为 60(足够存下所有字母种类)的数组 c1 和 c2,用于存储字符频率。其中 c1 用于记录字符串 t 中字符的频率,c2 用于记录当前滑动窗口内字符的频率。
设定好字母与频率数组下标的映射关系:小写字母 a-z 对应下标 0-25,大写字母 A-Z 对应下标 26-51。
使用变量 tot 来记录还需要匹配的字符种类数,当 tot = 0 代表当前滑动窗口对应的子串能够实现对 t 的覆盖,即任意字符满足 c2[i]≥c1[i]。
使用双指针 j 和 i 表示滑动窗口的左右边界。从前往后遍历字符串 s,在每个位置上更新字符频率数组 c2。若 c2 中字符的频率达到了 c1 中的字符频率,则将 tot 减 1,表示一个字符已经匹配完成。
每当右边界往后移动一步之后,滑动窗口会增加一个字符。此时我们检查左边界能否右移,同时不会使得 tot 变大。即每次右边界右移后,我们检查左边界 c2[j]>c1[j] 是否满足:
- 若满足:说明当前左边界指向字符并非必须,当前子串 s[j…i] 必然不是最短子串。我们让左边界 j 进行右移,并重复进行左边界 c2[j]>c1[j] 的检查,直到窗口不能再收缩
- 若不满足:说明当前窗口没有任何一个后缀字符串能够实现对 t 的覆盖,我们并不能对窗口实现收缩
每次对窗口移动完成后,我们检查当前 tot 是否为 0(对字符串 t 的覆盖是否完成),若为 0 则尝试用当前窗口对应的字符串 s[j…i] 更新 ans。
class Solution {public String minWindow(String s, String t) {int n = s.length(), tot = 0;int[] c1 = new int[60], c2 = new int[60];for (char x : t.toCharArray()) {if (++c1[getIdx(x)] == 1) tot++;}String ans = "";for (int i = 0, j = 0; i < n; i++) {int idx1 = getIdx(s.charAt(i));if (++c2[idx1] == c1[idx1]) tot--;while (j < i) {int idx2 = getIdx(s.charAt(j));if (c2[idx2] > c1[idx2] && --c2[idx2] >= 0) j++;else break;}if (tot == 0 && (ans.length() == 0 || ans.length() > i - j + 1)) ans = s.substring(j, i + 1);}return ans;}int getIdx(char x) {return x >= 'A' && x <= 'Z' ? x - 'A' + 26 : x - 'a';}
}