子串

子串指的是一个串中一部分连续元素的集合，是原串的一个子集

例题

和为k的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

分析

子数组可以被看作两个前缀作差，即arr = longPrefix - shortPrefix。因此目标值k可以通过前缀和的差求得，即k = sum[long] - sum[short]，移项有sum[long] = sum[short] + k. 同时注意到sum[long]的求得总是在sum[short]右侧发生，因此我们可以一边求前缀和并把加上k的结果（short + k）存入一张表，一边验证当前的前缀和long是否等于之前的某个存好的结果；这种情况每出现一次，就说明我们找到了至少一个（可能多个比如有两种short，每出现一次long就会产生两个）子数组。

综上，我们维护一张哈希表，以前缀和加kshort + k为键，以这个结果值出现的次数为值，一边求和一边维护的行为保证了当前计算的前缀和一定是之前就算好并保存的前缀和的后继，即一定是long。

代码如下

class Solution {
 	public int subarraySum(int[] nums, int k) {
        // 加入哈希的优化
        /*
        * 上述前缀和作差得到的一个子串可以视作 preLong - preShort = k
        * 即 preLong = preShort + k
        * 所以先遍历一遍生成一次前缀和，将该前缀和(preShort)加上k的结果作为key，查找这个key是否存在一个前缀和(preLong)与之相等
        * */
        Map<Integer, Integer> map = new HashMap<>(); // key: 前缀和  value: 对应前缀和出现的次数
        int sum = 0, ans = 0;
        // 注意需要保证必须是 long - k = short，即靠后的前缀和减去k的前缀和应当对于靠前的前缀和，即先加入map的前缀和
        map.put(sum, 1); // 前缀和0出现一次
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

滑动窗口最大值

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

分析

只维护一个一般的线性滑动窗口移动并更新其中最大值会超时。

解法一：使用最大堆。每个位置的数据有两个指标，下标和数值。想象这样一个情景，最初始的窗口在移动，我们每次移动窗口就往窗口中加入一个值，每次获取其中的最大值，只要这个最大值的下标仍在实际的滑动窗口范围内，我们仍然可以继续使用它，否则选拔一个新的最大值，以此类推。为此我们想到可以使用最大堆 ，堆顶元素即是最大值，**每次只需要确认堆顶元素是否还在滑动窗口内即可，如果不在，就一直出堆直到堆顶元素在滑动窗口内；滑动窗口移动，就是让新元素入堆。**在一开始初始化一个初始堆（初始窗口）并维护它即可。

堆中元素采用一个数对，即{在数组中的下标，数值}

代码如下

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // {index, value}
        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> {
            return o2[1] - o1[1]; // 降序如果前面大于后面返回负数
        }); // 使用堆
        for (int i = 0; i < k; i++) {
            heap.offer(new int[]{i, nums[i]}); // offer保证还是堆
        }
        int[] ans = new int[nums.length - k + 1];
        if (heap.isEmpty()) {
            return ans;
        }
        ans[0] = heap.peek()[1];
        for (int i = 1; i <= nums.length - k; i++) {
            heap.offer(new int[] {i + k - 1, nums[i + k - 1]}); 
            int[] tmp = heap.peek();
            while (tmp[0] < i || tmp[0] > i + k - 1) {
                heap.poll();
                tmp = heap.peek();
            }
            ans[i] = tmp[1];
        }
        return ans;
    }
}

解法二：使用单调队列。 TBD

最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

分析

本题可以采用滑动窗口算法。维护一个滑动窗口，不断向右扩张，如果左边界的字符超出了t中的所有字符，就收缩左边界直到窗口清零或左边界字符仍在t的字符范围内，每次窗口扩张前都要判断一下是否已经完成覆盖，记录覆盖结果中出现的最小子串。

tip：判断字符数量有没有到达要求可以再维护一个count数组记录t中字符出现的次数（也代指窗口中还需要出现的次数），0即为没有(窗口中不需要)出现；之后在维护窗口时，右边界纳入的字符即代表窗口覆盖到了它，因此count数组对应位置自减，如果一个位置的计数为负数，说明这个字符在子串中是多余的，左边界可以收缩将它踢出窗口（记得更新count）。如果count数组没有正数，说明当前窗口覆盖了t。

代码如下

class Solution {
   public String minWindow(String s, String t) {
        char[] sArr = s.toCharArray();
        int[] count = new int['z' - 'A' + 1];
        for (char c : t.toCharArray()) {
            count[c - 'A']++;
        }
        int left = 0, min = Integer.MAX_VALUE;
        int minStart = 0, minEnd = 0;
        String sub = "";
        for (int right = 0; right < sArr.length; right++) {
            char l = sArr[left], r = sArr[right];
            count[r - 'A']--;
            while (left < right && count[l - 'A'] < 0) {
                left++;
                count[l - 'A']++;
                l = sArr[left];
            }
            if (match(count)) {
                // find a substring
                if (min > right - left + 1) {
                    min = right - left + 1;
                    minStart = left;
                    minEnd = right;
                }
            }
        }
        // renew sub
        if (min < Integer.MAX_VALUE) {
            sub = s.substring(minStart, minEnd + 1);
        }
        return sub;
    }

    boolean match(int[] count) {
        for (int n : count) {
            if (n > 0) {
                return false;
            }
        }
        return true;
    }
}

(•‿•)