leetcode算法基础 第五天 滑动窗口

• 438. 找到字符串中所有字母异位词
• 713. 乘积小于K的子数组
• 209. 长度最小的子数组

题目
这道题找所有字符串的异位词，异位词是指字符串所有字符的全排列组合，所以滑动窗口的大小是固定的，需要两个hashmap，一个记录当前窗口内的字符以及value值，另一个记录要找的字符串的字符以及value值。需要注意的点是，滑动窗口内左边界在移出时的字符对应的value值为1时，删除hashmap中的该值，若大于1则将value减1。通过遍历不断判断两个hashmap是否一致。

//使用hashmap 固定滑动窗口大小，先初始化一个滑动窗口，每次向右移动一位，判断是否符合要求
public List findAnagrams(String s, String p) {
    List res = new linkedList<>();
    int m = s.length(), n = p.length();
    if (m < n) return res;
    Map s_map = new HashMap<>();
    Map p_map = new HashMap<>();
    for (int i = 0; i < n; i++) {  //初始化窗口以及目标字符串
        s_map.put(s.charAt(i), s_map.getOrDefault(s.charAt(i), 0) + 1);
        p_map.put(p.charAt(i), p_map.getOrDefault(p.charAt(i), 0) + 1);
    }
    if (s_map.equals(p_map)) res.add(0);
    for (int i = n; i < m ; i++) {
        if (s_map.get(s.charAt(i - n)) > 1){
            s_map.put(s.charAt(i - n), s_map.get(s.charAt(i - n)) - 1);
        } else {
            s_map.remove(s.charAt(i - n));
        }
        s_map.put(s.charAt(i), s_map.getOrDefault(s.charAt(i), 0) + 1); //左边界移出，右边界移进
        if (s_map.equals(p_map)) res.add(i - n + 1);
    }
    return res;
}

题目
这道题要找乘积小于 k 的连续的子数组的个数，所以不能用回溯的方法。
知道是滑动窗口，但是没写出来。看了大佬们的思路写了一遍，关键是要理解
r-l+1，以及为什么不会重复
每一次循环找的是以r为右边界的子数组，r一直在变，所以一定不重复
比如5，2，6此时满足条件，此时右边界为6，要找的数组就是[6],[6,2],[6,2,5]
每个长度的数组只有一个，相当于求这个l…r的闭区间长度
边界处理：当k为0或者1直接返回0
这样也保证了在收缩左边界时候不会越界，因为l收缩到r之后prod就为1了，一定小于k，会退出内层循环
此时表示没有合适的区间满足乘积小于k，此时l++之后l=r+1的，r-l+1也正好是0

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int prod = 1, ans = 0, left = 0;
    for (int right = 0; right < nums.length; right++) {
        prod *= nums[right];
        while (prod >= k) prod /= nums[left++];
        ans += right - left + 1;
    }
    return ans;
}

题目
这道题就是最简单的滑动窗口的用法，首先右边界右移，直到满足要求，记录此时的窗口长度，然后左边界右移，只要不满足条件就停止右移，以此类推直到右边界达到数组最右端，且窗口满足条件。

public int minSubArrayLen(int target, int[] nums) {
    int re = Integer.MAX_VALUE;
    int sum = 0; int left = 0;
    for (int right = 0;right < nums.length; right++){
        sum += nums[right];
        if (sum >= target) {
            re = Math.min(re, right - left + 1);
            while (left <= right) {
                sum -= nums[left++];
                if (sum >= target) {
                    re = Math.min(re, right - left + 1);
                } else break;
            }
        }
    }
    return re == Integer.MAX_VALUE ? 0 : re;
}