滑动窗口 --面试经典150题

长度最小的子数组(medium)

做题过程

用两个判断分别管理左右边界，实际上是错误的结构，需要更多的判断防止越界。

算法概述

本题要求为计算和大于等于目标值的最短的子数组的长度。

时间复杂度为O(n)
空间复杂度为O(1)

JAVA

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0;
        int sum = 0; 
        int ans = Integer.MAX_VALUE;
        
        // 注意：数组有可能是空的，提前检查
        if (nums.length == 0) {
            return 0;
        }

        while (r < nums.length) {
            // 增加 sum 和右指针
            sum += nums[r];
            
            // 如果当前和大于等于 target，移动左指针来缩小窗口
            while (sum >= target) {
                ans = Math.min(ans, r - l + 1);  // 计算窗口大小
                sum -= nums[l];  // 移动左指针
                l++;
            }
            
            // 移动右指针
            r++;
        }
        
        // 如果找不到符合条件的子数组，返回 0
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

总结

右边界更新应该在左边界的外部 ，左边界需要 另外一个循环 来控制移动，两者不能平行。

串联所有单词的子串(hard)

做题过程

没有写出来，想到了肯定是哈希表，但是具体实现还是没有整理好思路，怎么规划滑动窗口的移动才是这道题的难点所在。

算法概述

原题

本题要求为给出一个字符串数组和一个目标字符串，查找由字符串数组以各种顺序拼接而成的字符串在目标字符串的起始位置。需要使用 哈希表 统计经过的字符串数组元素，以及控制 滑动窗口 移动来避免问题。

时间复杂度为：滑动窗口有n个起始点的可能
空间复杂度为：哈希表

JAVA

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans=new ArrayList<>();
        int n=words.length, m=words[0].length();
        int ls=s.length();
        // 外部循环控制滑动窗口的起始点
        for(int i=0;i!=m;++i){
            // 滑动窗口右边界是否已经超出字符串
            if(i+m*n>ls) break;
            Map<String,Integer> map=new HashMap<>();
            // 初始第一个滑动窗口
            // 读取目标字符串中的单词
            for(int j=0;j!=n;++j){
                String word=s.substring(i+j*m,i+(j+1)*m);
                map.put(word,map.getOrDefault(word,0)+1);
            }
            // 减去频次
            for(String word:words){
                map.put(word,map.getOrDefault(word,0)-1);
                if(map.get(word)==0){
                    map.remove(word);
                }
            }
            // 滑动窗口后续移动
            for(int start=i;start<ls-m*n+1;start+=m){
                // 当滑动窗口开始移动时
                if(start!=i){
                    // 右边界扩张
                    String word=s.substring(start+(n-1)*m,start+n*m);
                    map.put(word,map.getOrDefault(word,0)+1);
                    // 对应值可能出现-1的情况，所以这里的判断是必须的
                    if(map.get(word)==0) map.remove(word);
                    // 左边界收缩
                    word=s.substring(start-m,start);
                    map.put(word,map.getOrDefault(word,0)-1);
                    // 移除相应元素
                    if(map.get(word)==0){
                        map.remove(word);
                    }
                }
                if(map.isEmpty()==true) ans.add(start);
            }
        }
        return ans;
    }
}

总结

这道题的难点之处也不在于算法，而在于组织代码结构。这里对滑动窗口的移动 不是解法实现的主体 ，而 只是其中的一个循环 ，而外部循环则用来移动滑动数组的起始点，这是很难想到的，需要理解背后是如何 拆分问题 ，判断是将字符串的长度和字符串个数作为外部还是内部循环是很重要的✅。