和为k的子数组

法1：暴力

暴力方法，可以过所有用例，复杂度是O(n²)。
遍历两轮，外层循环的r是右侧区间，内层循环是从r到0，不断的加和并判断。
本质上是遍历从[r-1, r]到[r-2, r]到[r-2, r]这样的区间。

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int len = nums.length;
        for(int r = 0; r < len; r++){
            int sum = 0;
            for(int l = r; l>=0; l--){
                sum += nums[l];
                if(sum == k) count++;
            }
        }
        return count;
    }
}

法2：前缀和

来自力扣：

一般来说，看到连续子数组元素相关的，基本就是滑动窗口或者前缀和。

前缀和满足如下操作：
sum[n + 1] = nums[0] + nums[1] + … + nums[n]
nums[n] = sum[n + 1] – sum[n]

用一个哈希表 map 统计 sum[j] 的个数。哈希表的 key 是 sum[j]，value 是值为 sum[j] 的前缀和的个数。
算法的过程即从小到大遍历前缀和数组，遍历的过程维护哈希表，通过判断target存在的个数，即可加和出结果。

引用牛客的题解，注明为什么这样可以不重不漏：

问：为什么这样做可以不重不漏地计算？
答：暴力做法是，外层循环枚举 j，内层循环枚举 i，如果 s[j]−s[i]=k，那么答案加一。我们保留了「外层循环枚举 j」这个过程，把内层循环用哈希表优化成了 O(1)，所以本质是对暴力算法的哈希表优化。既然暴力算法是不重不漏地计算，那么优化做法也是不重不漏地计算。
作者：灵茶山艾府

public class Solution {
    public int subarraySum(int[] nums, int k) {
        // 先维护出前缀和数组
        int[] preSum = new int[nums.length + 1];
        for(int i = 0; i < nums.length; i++){
            preSum[i+1] = nums[i] + preSum[i];
        }
        
        // 题目要求的目标 可以转化为求s[j] - s[i] = k 满足的解个数
        // 可以借助哈希表存储已经遍历过的元素，即出现过的 preSum[i]
        // 当我们遍历到 preSum[j] 的时候，我们就是要找在这之前，有多少个 preSum[i]满足等于preSum[j] - k
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int sj:preSum){
            int target = sj - k; // 要找的目标是这个
            if(map.containsKey(target)){ //如果存在
                res+= map.get(target);
            }
            // 将当前前缀和存入map（如果已存在则次数+1，否则初始化为1）
            map.put(sj, map.getOrDefault(sj, 0) + 1);
        }
        return res;
    }
}

滑动窗口的最大值

使用单调队列，摘自牛客：

窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决以上问题。遍历数组时，每轮保证单调队列 deque ：
deque 内仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 nums[i−1] ，需将 deque 内的对应元素一起删除。
deque 内的元素非严格递减 ⇒ 每轮窗口滑动添加了元素 nums[j+1] ，需将 deque 内所有 <nums[j+1] 的元素删除。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 2) return nums;
        Deque<Integer> deq = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < nums.length; i++){
            // 如果队尾的数 小于当前数 那就让队尾的数出队 保持住队列所有数字都≥当前数
            while(!deq.isEmpty() && nums[deq.peekLast()] < nums[i]){
                deq.pollLast();
            }
            // 处理之后 队头的下标一定会是最大值
            deq.addLast(i);

            // 如果队头已经不在窗口内了 要去掉
            if(deq.peekFirst() < i - k + 1){
                deq.pollFirst();
            }
            if(i - k + 1 >= 0){
                res[i-k + 1] = nums[deq.peekFirst()];
            }
        }
        return res;
    }
}

最小覆盖子串

滑动窗口问题。我们要用一个窗口 [l, r] 扫描 s，在窗口内维护 t 的字符需求情况。滑动窗口方法：

• 先统计 t 中每个字符的数量，存入数组/哈希表 cnt。
• 用变量 k 表示当前还需要多少字符。
• 先扩展右边界，循环迭代k–，和cnt–，直到k=0，说明窗口扩大完毕，开始考虑缩小。
• k=0，先判断bestleft和bestlen的情况（当前窗口是否比上一个窗口更好）。
• l++，对应的cnt需要++，同时需要维护是否k需要++。

class Solution {
    public String minWindow(String s, String t) {
        // 如果s和t相等，直接返回s
        if (s.equals(t)) return s;
        
        int n = s.length();
        int k = t.length(); // k表示还需要匹配的字符总数
        
        // 使用数组记录t中每个字符的需求量
        int[] cnt = new int[128];
        
        // 统计t中每个字符的出现次数
        for (char x : t.toCharArray()) {
            cnt[x]++;
        }
        
        int left = 0, right = 0; // 滑动窗口的左右指针
        int bestLen = Integer.MAX_VALUE; // 记录最小窗口长度
        int bestStart = -1; // 记录最小窗口的起始位置
        
        // 开始滑动窗口遍历
        while (right < n) {
            char rightChar = s.charAt(right);
            
            // 减少当前字符的需求量
            cnt[rightChar]--;
            
            // 如果减少后需求量仍大于等于0，说明这个字符是t中需要的
            // 成功匹配了一个字符，k减1
            if (cnt[rightChar] >= 0) {
                k--;
            }
            
            // 当k==0时，说明当前窗口[l, r]已经包含了t的所有字符
            // 尝试收缩左边界来寻找更小的窗口
            while (k == 0) {
                // 计算当前窗口长度
                int currentLen = right - left + 1;
                
                // 如果当前窗口更小，更新最优解
                if (currentLen < bestLen) {
                    bestLen = currentLen;
                    bestStart = left;
                }
                
                char leftChar = s.charAt(left);
                
                // 恢复左边界字符的需求量
                cnt[leftChar]++;
                
                // 如果恢复后需求量大于0，说明移走了一个关键字符
                // 窗口不再满足包含t的所有字符，k加1
                if (cnt[leftChar] > 0) {
                    k++;
                }
                
                // 左指针右移，收缩窗口
                left++;
            }
            
            // 右指针右移，扩展窗口
            right++;
        }
        
        // 如果找到了符合条件的窗口，返回子串；否则返回空字符串
        return bestStart == -1 ? "" : s.substring(bestStart, bestStart + bestLen);
    }
}