算法Day2|209-长度最小的子数组;59-螺旋矩阵;977-有序数组的平方;904-水果成篮;76-最小覆盖子串

前言

• 题目:209-长度最小的子数组 | 2024-10-16 | 通过
• 题目2：螺旋矩阵II | 2024-10-16 | 未通过
• 题目:904-水果成篮 | 2024-10-16 | 未通过
• 题目:76-最小覆盖子串 | 2024-10-16 | 未通过

1、题目1：209-长度最小的子数组

题目：leetcode.cn/problems/mi…

难度：中等

给定一个含有 n ****个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 ****target ****的长度最小的 子数组[nums(l), nums(l+1), ..., nums(r-1), nums(r)] ，并返回其长度 。 如果不存在符合条件的子数组，返回 0 。

难度：中等

案例：

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

思路：

• 滑动窗口解决即可，但是滑动窗口的解题思路老是忘记。（代码随想录）

滑动窗口：所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

暴力解法，用两个 for 循环不断搜索区间的过程；

而滑动窗口使用的是一个 for 循环完成这个操作；

• 暴力解法中：两个 for 循环，一个for循环表示开始位置，另一个表示结束位置，并记录下区间的最小值；

• 滑动窗口中：你想，只用一个 for 循环，那这个循环的索引就表示滑动窗口的结束位置。

  • 那么问题来了，如何移动滑动窗口的开始位置？？？？

  • 以下图寻址来举例，可以看到开始位置是找到第一个满足区间的数字后，开始往后压缩，直到不满足条件

    • 

  • 那要解决滑动窗口，需要确定三个点：

    • 1、窗口内是什么？--> 满足 >= s 的长度最小的区间数组
    • 2、如何移动窗口的起始位置？-->如果当前窗口的值>=s,窗口就要向前移动
    • 3、如何移动窗口的结束位置？--> for 循环的索引

  • 解题的关键在于窗口的起始位置如何移动。

whlie（sum >= s）{
    length = （j-i+1）；// 序列长度
    res = min(length,res);
    sum = sum -nums[i++];
}

解题：

    public static int minSubArrayLen(int target, int[] nums) {

        int res = nums.length +1 ;
        int sum = 0; // 累计和
int j = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target){
                int sublength = (i - j) + 1;
                res = Math.min(sublength,res);
                sum -=nums[j++];
            }
        }
        return res==nums.length+1? 0:res;
    }

    public static void main(String[] args) {
        int[] ints = {1,1,1,1,1,1,1,1};
        System.out.println(minSubArrayLen(11,ints));
    }

}

2、题目2：螺旋矩阵II

题目：leetcode.cn/problems/sp…

难度：中等

解题思路：

• 初始化一个n*n 大小的矩阵，然后模拟整个向内环绕的填入过程。

• 非常清晰的思路，不断缩小上下边界

• 定义 i 是移动横坐标，j 是列坐标移动

public int[][] generateMatrix(int n){
    int left = 0;
    int right = n-1;
    int top = 0;
    int bottom = n-1;

    int target = 1;
    int[][] nums = new int[n][n];
    while (target <= n*n){
        // 开始从左到右移动，高度不变
for (int j = left; j <=right ; j++) {
            nums[top][j] = target++;
        }
        top++;
        // 开始从上到下移动
for (int i = top; i <= bottom; i++) {
            nums[i][right] = target++;
        }
        right--;
        // 右边到左边
for (int j = right; j >= left; j--) {
            nums[bottom][j] = target++;
        }
        bottom--;
        // 从下到上
for (int i = bottom; i >= top ; i--) {
            nums[i][left] = target++;
        }
        left++;
    }
    return nums;
}

3、题目拓展：904-水果成篮

滑动窗口的题目得多刷几道，例如本题的水果成篮，记住这个思想。

题目：leetcode.cn/problems/fr…

难度：中等

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1 ：
输入： fruits = [1  ,  2  ,  1]
输出： 3
解释： 可以采摘全部 3 棵树。

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

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

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

思路：

滑动窗口，for 循环的结束即遍历索引；

那如何定位区间开启，即篮子中的种类超过2的时候，就需要收缩窗口。

种类为2的话，可以使用 set 结构判定。

但是用 set 发现无法缩小左边区间，用map 来记录下元素出现的个数。

Slow 指针不断从0往后移动，每移动一下，就从map中获取这个元素，对其个数减少1操作，如果为0，则删除该元素。

public class Number_904 {

    public static void main(String[] args) {
        int[] ints = {3,3,3,1,2,1,1,2,3,3,4};
        System.out.println(totalFruit(ints));
    }

    public static int totalFruit(int[] fruits) {
        if(fruits.length ==0){
            return 0;
        }

        int slow = 0;
        int length = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < fruits.length; i++) {
            map.put(fruits[i],map.getOrDefault(fruits[i],0) + 1);
            while (map.size()>2){
                // 缩减左边界
map.put(fruits[slow],map.get(fruits[slow]) - 1);
                if(map.get(fruits[slow]) == 0){
                    map.remove(fruits[slow]);
                }
                slow++;
            }
            length = Math.max(length,i-slow+1); //更新最大区间
}
        return length;
    }
}

4、题目拓展：76-最小覆盖子串

再来一道题搞一搞，这题是经典的最小子串问题。

一刷可以了解下。

题目：leetcode.cn/problems/mi…

难度：困难

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

示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。

代码：

public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> windows = new HashMap<>();

    for (char aChar : t.toCharArray()) {
        need.put(aChar,need.getOrDefault(aChar,0)+1);
    }

    int valid =0;
    // 记录左右指针
int left =0;
    int right = 0;
    // 记录最小覆盖子串的起始索引及长度
int start = 0,len =Integer.MAX_VALUE;

    while (right < s.length()){
        // 窗口内的数据更新，我们需要记录有效数。valid，
 // 且窗口内必须是有目标值，才进行存储，否则过滤
char c = s.charAt(right++);
        if(need.containsKey(c)){
            windows.put(c,windows.getOrDefault(c,0)+1);
            // 有效数是我们判断窗口移动的依据
if(windows.get(c).equals(need.get(c))){
                valid++;
            }
        }
        // 有效字相等，我们可以收缩窗口
while (valid == need.size()){
            // 更新最小覆盖子串
if(right - left < len){
                start = left;
                len = right- left;
            }
            // 缩小窗口 d 是将移出窗口的字符
char d = s.charAt(left);
            left++;
            if(need.containsKey(d)){
                if(windows.get(d).equals(need.get(d))){
                    valid--;
                }
                windows.put(d,windows.get(d)-1);
            }
        }
    }
    if(len == Integer.MAX_VALUE){
        return "";
    }
    return s.substring(start,start+len+1);
}

5、数组总结

1、数组的刷题过程中，从掌握基本的数据结构之外，例如 int[] 数组的 length，string 的length() ,list的 size() 等方法不要混淆。

2、二分查找是非常重要的，注意边界条件，选择左闭右闭的写法；

3、移除元素中，常常用到快慢指针的思想，可以通过一次循环跳过某些元素，进行移除；

4、有序数组平方：也是通过双指针的思想，只不过一个指针从左，另一个指针从右开始

5、滑动窗口在这章初露锋芒，这个后面还是会出现，涉及到子串问题，还是非常重要的，后面再做总结，一次掌握不太可能

6、螺旋指针，根据k神的写法，非常优雅。