C/C++教程

Leetcode 刷题笔记(三) —— 数组类型解题方法二:滑动窗口

本文主要是介绍Leetcode 刷题笔记(三) —— 数组类型解题方法二:滑动窗口,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

数组

  • 滑动窗口
    • 209. 长度最小的子数组
    • 904. 水果成篮
    • 76. 最小覆盖子串(困难)
    • 总结

刷题路线来自 :代码随想录

滑动窗口

209. 长度最小的子数组

Leetcode 链接
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:
输入:target = 4, nums = [1,4,4]
输出:1

示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
题解:
滑动窗口区间变化时,更新窗口内数的和 ;
在 sum 不够 target 大时扩大滑动窗口;
在 sum 大于等于 target 时缩小滑动窗口,并且更新长度最小值;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int minLen = Integer.MAX_VALUE;   // 返回长度最小的子数组
        int sum = 0;  
        while (right < nums.length) {
        	// sum 小于 target 并且没有越界时,右指针右移扩大滑动窗口
            while (sum < target && right < nums.length) {
                sum += nums[right++];
            }
            // sum 大于 target 时,表示找到满足条件的子数组,更新最小长度值,左指针右移缩小滑动窗口
            while (sum >= target) {
                minLen = Math.min(minLen, right - left);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

**化简后:**使用滑动窗口右指针遍历数组,一直在扩大窗口,直到满足题目条件 sum >= target 时停下。这时左指针右移缩小滑动窗口,并且更新最小长度。下边代码可作为滑动窗口解题模板

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int minLen= Integer.MAX_VALUE;
        int sum = 0;
        for (int right = 0; right < nums.length; right ++) {
            sum += nums[right];
            // 不满足题目需要的条件就不会进入 while 循环,右指针可一直右移扩大窗口,直到满足条件进入while循环,这是才去更新我们要找的最小长度值
            while (sum >= target) {
                minLen= Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen== Integer.MAX_VALUE ? 0 : minLen;
    }
}

904. 水果成篮

Leetcode 链接
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  1. 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  2. 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  3. 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。 给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 2:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。
题解: 动图

  1. 右指针遍历数组,扩大滑动窗口
  2. 滑动窗口变化时,更新 map<水果的类型,该类型的数量>, map记录滑动窗口内的水果种类和数量,也表示篮子中放的所有水果
  3. map 中水果种类大于 2 时表示两个篮子已经放不下了,第三类水果暂时放到一个新篮子里,左指针右移缩小滑动窗口,直到清空一个篮子,也就是map 中只有两类水果时再开始向右移动右指针扩大滑动窗口。
  4. 没有进入while 循环时是满足题目条件的,也就是两个篮子能放下水果,这个时候每次遍历需要更新最大长度
class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int maxLen = 0;
        // map 记录每种水果的个数
        Map<Integer, Integer> map = new HashMap<>();
        for (int right = 0; right < fruits.length; right ++) {
            // 右指针位置的水果放入 map
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            // 滑动窗口内水果种类大于 2 个时, 左指针右移缩小窗口,直到清空一个篮子为止
            while(map.size() > 2) {
                map.put(fruits[left], map.get(fruits[left]) - 1);
                if (map.get(fruits[left]) == 0) {
                	// 左指针位置水果种类数量为0 时,移除 map 中该类水果
                    map.remove(fruits[left]);
                }
                left++;
            }
            // 扩大窗口的时候更新 最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

使用数组

class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int maxLen = 0;
        int[] count = new int[fruits.length];
        int size = 0;
        for (int right = 0; right < fruits.length; right ++) {
            if (count[fruits[right]] == 0) size++;
            count[fruits[right]]++;
            // 滑动窗口内水果种类大于 2 个时
            while (size > 2) {
                count[fruits[left]]--;
                if (count[fruits[left]] == 0) {
                    size--;
                }
                left++;
            }
            // 扩大窗口的时候更新 最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

76. 最小覆盖子串(困难)

Leetcode 链接
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”

示例 2:
输入:s = “a”, t = “a”
输出:“a”

示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

题解:

  1. 在缩小滑动窗口时更新返回数据,满足滑动窗口的长度小于最小长度时更新,需要维护:最小长度 minLen、覆盖字串 res
  2. 在滑动窗口中的字符串成功覆盖子串 t 时缩小窗口
  3. 什么时候滑动窗口中的字符串成功覆盖子串 t ?,
    mapT 记录子串 t 中字符和出现次数;windowsMap 记录滑动窗口中的字符串中含子串 t 中的字符和出现次数。
    valid 记录滑动窗口中能覆盖的字符种类数。windowsMap 和 valid 需要动态维护,随着滑动窗口的缩小和扩大变化。当vaild 等于 mapT 中记录的子串 t 时说明覆盖子串 t。
class Solution {
    public String minWindow(String s, String t) {
        int left = 0;
        Map<Character, Integer> mapT = new HashMap<>();
        Map<Character, Integer> windowsMap = new HashMap<>();
        int minLen = Integer.MAX_VALUE;
        String res = ""; 
        int valid = 0;  // 滑动窗口中能覆盖的字符种类数
        for (char ch : t.toCharArray()) {
            mapT.put(ch, mapT.getOrDefault(ch, 0) + 1);
        }
		
        for (int right = 0; right < s.length(); right++) {
            char r = s.charAt(right);
            if (mapT.containsKey(r)) {
                // 字串 t 中有右指针位置字符, 保存滑动窗口字符的Map记录该字符出现的次数 
                windowsMap.put(r, windowsMap.getOrDefault(r, 0) + 1);
                if (windowsMap.get(r).equals(mapT.get(r))) {
                    valid++;
                }
            }
            // 成功覆盖字串,缩小窗口,更新最小字串
            while (mapT.size() == valid) {
                // 更新最小字串
                if (right - left < minLen) {
                    res = s.substring(left, right + 1);
                    // 更新最小长度值
                    minLen = Math.min(minLen, right - left + 1);
                }
                // 记录下左指针位置字符,缩小窗口
                char l = s.charAt(left);
                left++;
                // 要是左指针位置字符是字串中的字符 A...BBB...C..A
                if (windowsMap.containsKey(l)) {
                    if (mapT.get(l).equals(windowsMap.get(l))) {
                        // 若子串为 ABC, 那么 A...BBB...C..A,只有是BBB最后一个时,才需要 valid--,故要做此判断
                        valid--;
                    }
                    windowsMap.put(l, windowsMap.get(l) - 1);
                }
            }
        
        }
        return res;
    }
}

总结

此类题通用套路:

		// 左指针
        int left = 0;
        // 需要动态维护的...
		// ...与 while 循环中满足滑动窗口缩小的条件相关,同时与返回的数据相关,围绕这两个点思考随着滑动窗口变化的同时,需要动态维护的数据
		
        // 遍历右指针
        for (int right = 0; right < nums.length; right++) {
            // 动态维护数据

			
            while () {
                // 满足缩小滑动窗口的条件

                // 左指针右移缩小滑动窗口
                left++;
            }
        }

        return ...;

题目的难点与解题的方法:

  1. 分析缩小滑动窗口的条件是什么?需要动态维护那些数据?
  2. 什么时候更新返回数据,是在缩小滑动窗口时还是扩大滑动窗口时?
  3. 要更新返回数据需要在滑动窗口中动态维护的数据是什么?
这篇关于Leetcode 刷题笔记(三) —— 数组类型解题方法二:滑动窗口的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!