代码随想录算法训练营第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

数组基础

1、数组定义：数组是存放在连续内存空间上的相同类型数据的集合。

特点：

• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的

2、数组的元素是不能删的，只能覆盖。

977.有序数组的平方

1、题目链接：. - 力扣（LeetCode）

2、文章讲解：代码随想录

3、视频讲解： 双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili

4、前提条件：非递减顺序 排序的整数数组

5、难点：

6、遵循点：数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

双指针解法

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    // 双指针解法
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        // 先将结果数组初始化为nums数组
        int newResult[] = new int[nums.length];
        int index = nums.length - 1;
        while (left <= right) {
            // 比较左右两个数的大小，将较大的数放入结果数组，并将指针向前移动
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                newResult[index] = nums[left] * nums[left];
                left++;
            } else {
                newResult[index] = nums[right] * nums[right];
                right--;
            }
            index--;
        }
        return newResult;
    }
}

209. 长度最小的子数组

1、题目链接：. - 力扣（LeetCode）

2、文章讲解：代码随想录

3、视频讲解：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

4、题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

5、注意点：在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

滑动窗口解法

没有改变元素的相对位置

• 时间复杂度：O(n)
• 空间复杂度：O(1)

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++;
            }
        }
        // 如果数组和小于目标值，返回0
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

59、螺旋矩阵II

1、题目链接：. - 力扣（LeetCode）

2、文章讲解：代码随想录

3、视频讲解：一入循环深似海 | LeetCode：59.螺旋矩阵II_哔哩哔哩_bilibili

4、题目：

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

5、难点：不会控制循环不变量

6、遵循点：

要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)

class Solution {
    // 左闭右开原则
    public int[][] generateMatrix(int n) {
        // 控制循环次数
        int loop = 0;
        int[][] matrix = new int[n][n];
        // 每次循环的开始点（start，start）
        int start = 0;
        int count = 1;
        int i, j;
        // 循环条件
        while (loop++ < n / 2) {
            // 模拟上侧从左到右的循环
            for (j = start; j < n - loop; j++) {
                matrix[start][j] = count++;
            }
            // 模拟右侧从上到下的循环
            for (i = start; i < n - loop; i++) {
                matrix[i][j] = count++;
            }
            // 模拟下侧从右到左的循环
            for (; j >= loop; j--) {
                matrix[i][j] = count++;
            }
            // 模拟左侧从下到上的循环
            for (; i >= loop; i--) {
                matrix[i][j] = count++;
            }
            start++;
        }
        if (n % 2 == 1) {
            matrix[start][start] = count++;
        }
        return matrix;

    }
}