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

超、凢脫俗 2024-04-23 03:49 30阅读 0赞

#### 数组基础 ####

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

**特点：**

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

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

#### 977.有序数组的平方 ####

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

2、文章讲解：[代码随想录][Link 1]

3、视频讲解： [双指针法经典题目 | LeetCode：977.有序数组的平方\_哔哩哔哩\_bilibili][_ 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）][. - _LeetCode 1]

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

3、视频讲解：[拿下滑动窗口！ | LeetCode 209 长度最小的子数组\_哔哩哔哩\_bilibili][_ 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）][. - _LeetCode 2]

2、文章讲解：[代码随想录][Link 3]

3、视频讲解：[一入循环深似海 | LeetCode：59.螺旋矩阵II\_哔哩哔哩\_bilibili][_ 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;
    
        }
    }

[. - _LeetCode]: https://leetcode.cn/problems/squares-of-a-sorted-array/
[Link 1]: https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
[_ LeetCode_977._bilibili]: https://www.bilibili.com/video/BV1QB4y1D7ep
[. - _LeetCode 1]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[Link 2]: https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
[_ LeetCode 209 _bilibili]: https://www.bilibili.com/video/BV1tZ4y1q7XE
[. - _LeetCode 2]: https://leetcode.cn/problems/spiral-matrix-ii/
[Link 3]: https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
[_ LeetCode_59._II_bilibili]: https://www.bilibili.com/video/BV1SL4y1N7mV/