●day 2 第一章数组part02（1.23）

第一题：209.长度最小的子数组

解题思路

本题要在给定的正整数数组中找出总和大于等于目标值 target 的长度最小的子数组，并返回其长度。若不存在这样的子数组，则返回 0。这里采用滑动窗口的方法来解决，其核心思路是利用两个指针（left 和 right）动态地维护一个子数组，不断调整子数组的范围，以找到满足条件的最小长度子数组。

具体步骤如下：

初始化变量： left：滑动窗口的左指针，初始化为 0，表示从数组的起始位置开始。sum：用于记录当前滑动窗口内元素的总和，初始化为 0。result：用于存储满足条件的最小子数组的长度，初始化为 Integer.MAX_VALUE，方便后续比较更新。
移动右指针：使用 for 循环移动右指针 right，每次将 nums[right] 加入到 sum 中，不断扩大滑动窗口的范围。
调整左指针：当 sum 大于等于 target 时，说明当前滑动窗口内的元素总和满足条件。计算当前滑动窗口的长度 right - left + 1，并使用 Math.min 函数更新 result，取当前 result 和新长度中的较小值。接着将 nums[left] 从 sum 中减去，并将左指针 left 右移一位，缩小滑动窗口的范围，继续检查新的窗口是否仍然满足条件。
返回结果：若遍历完整个数组后，result 仍然等于 Integer.MAX_VALUE，说明不存在满足条件的子数组，返回 0；否则返回 result。

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

第二题：59.螺旋矩阵II

解题思路

本题要求生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的 $n \times n$ 正方形矩阵。解题的关键在于按顺时针方向逐层填充矩阵元素，从外层到内层依次进行。

具体步骤

初始化矩阵和变量：创建一个的二维数组 nums 用于存储矩阵元素。startX 和 startY 分别表示当前层的起始行和起始列，初始值都为 0。loop 表示当前是第几层循环，初始值为 1。offset 用于控制每一层循环的边界，初始值为 1。count 用于记录当前要填充的数字，初始值为 1。
循环填充矩阵层：使用 while 循环，循环条件为 loop <= n / 2。每一次循环填充矩阵的一层，从外层向内层进行。在每一层中，按顺时针方向依次填充四个边：从左到右：固定行 startX，列 j 从 startY 递增到 n - offset，将 count 赋值给 nums[startX][j]，并将 count 加 1。从上到下：固定列 j，行 i 从 startX 递增到 n - offset，将 count 赋值给 nums[i][j]，并将 count 加 1。从右到左：固定行 i，列 j 从当前位置递减到 startY，将 count 赋值给 nums[i][j]，并将 count 加 1。从下到上：固定列 j，行 i 从当前位置递减到 startX，将 count 赋值给 nums[i][j]，并将 count 加 1。完成一层的填充后，loop 加 1，offset 加 1，startX 和 startY 都加 1，进入下一层的填充。
处理奇数阶矩阵的中心元素：如果 n 是奇数，矩阵的中心元素在循环结束后还未填充，需要单独处理。此时 startX 和 startY 正好指向矩阵的中心位置，将 count 赋值给 nums[startX][startY]。
返回结果：填充完成后，返回生成的矩阵 nums。

循环次数为什么是 $n/2$

可以把矩阵想象成一个洋葱，每一层循环就像是剥掉一层洋葱皮。对于一个 $n \times n$ 的矩阵，当 $n$ 为偶数时，矩阵可以被完整地分成 $n/2$ 层，每层都需要进行填充操作。例如，当 $n = 4$ 时，矩阵可以分成两层，先填充外层，再填充内层。当 $n$ 为奇数时，虽然最中心有一个单独的元素，但除了这个中心元素外，其余部分同样可以分成 $(n - 1)/2$ 层，而循环次数依然可以用 $n/2$ 来表示（因为在 Java 中整数除法会向下取整）。所以，循环次数设置为 $n/2$ 可以确保对矩阵的每一层进行正确的填充。

class Solution {
    public int[][] generateMatrix(int n) {
       int[][] nums = new int[n][n];
       int startX = 0,startY = 0;
       int i,j;
       int loop = 1,offset = 1,count = 1;
       while(loop <= n / 2){
            for(j = startY;j < n - offset;j++){
                nums[startX][j] = count++;
            }
            for(i = startX;i < n - offset;i++){
                nums[i][j] = count++;
            }
            for(;j > startY;j--){
                nums[i][j] = count++;
            }
            for(;i > startX;i--){
                nums[i][j] = count++;
            }
            loop++;
            offset++;
            startX++;
            startY++;
       }
       if(n % 2 == 1){
            nums[startX][startY] = count;
       }
       return nums;
    }
}

#螺旋矩阵##滑动窗口双指针问题##算法刷题#