LeetCode HOT100（四）字串

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';}
}