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

977. 有序数组的平方

题目链接：977. 有序数组的平方
文档讲解：代码随想录
状态：so easy

刚开始看到题目第一反应就是平方之后进行排序，数据量在$10^4$，可以使用O(nlogn)的排序。但是更好的方式是使用双指针，详见题解。

题解

双指针题解：

public int[] sortedSquares(int[] nums) {// 初始化指向数组头和尾的指针int front = 0, rear = nums.length - 1;// 初始化结果数组的最后一个索引int index = nums.length - 1;// 创建一个与输入数组长度相同的结果数组int[] res = new int[nums.length];// 当头指针没有超过尾指针时，继续循环while (front <= rear) {// 比较头指针和尾指针指向的数的平方大小if (nums[front] * nums[front] > nums[rear] * nums[rear]) {// 如果头指针指向的数的平方较大，则将其放入结果数组的当前索引位置res[index] = nums[front] * nums[front];// 头指针向右移动一位front++;} else {// 如果尾指针指向的数的平方较大或相等，则将其放入结果数组的当前索引位置res[index] = nums[rear] * nums[rear];// 尾指针向左移动一位rear--;}// 将结果数组的索引向左移动一位index--;}// 返回排序后的平方数组return res;
}

209. 长度最小的子数组

题目链接：209. 长度最小的子数组
文档讲解：代码随想录
状态：so easy

思路：因为是连续子数组，所以可以考虑滑动窗口求和，然后左右放缩找满足条件的最小长度。

题解

双指针题解

public int minSubArrayLen(int target, int[] nums) {// 初始化当前子数组的和int sum = 0;// 初始化最小长度为一个很大的值int minLen = Integer.MAX_VALUE;// 初始化两个指针i和j，i为当前遍历到的数组位置，j为子数组的起始位置for (int i = 0, j = 0; i < nums.length; i++) {// 将当前元素加入到子数组的和中sum += nums[i];// 当子数组的和大于等于目标值时，执行下面的循环while (sum >= target) {// 更新最小长度为当前子数组的长度minLen = Math.min(minLen, i - j + 1);// 将子数组起始位置的元素从和中减去，然后将子数组的起始位置向右移动一位sum -= nums[j++];}}// 如果最小长度仍然为初始值，说明没有找到满足条件的子数组，返回0// 否则返回最小长度return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

59. 螺旋矩阵 II

题目链接：59. 螺旋矩阵 II
文档讲解：代码随想录
状态：还行，刚开始卡了一小会儿。

思路：这个算法的目标是生成一个 n x n 的螺旋矩阵，其中矩阵元素按顺时针方向依次递增。我们可以利用四个边界变量（top、left、right、bottom）来逐步收缩矩阵的边界，并在每一步按顺时针方向填充矩阵。

题解

public int[][] generateMatrix(int n) {// 创建一个n x n的矩阵int[][] matrix = new int[n][n];// 初始化填入矩阵的数字int num = 1;// 初始化边界变量int top = 0, left = 0, right = n - 1, bottom = n - 1;// 当矩阵的上下边界和左右边界没有重叠时，继续填充矩阵while (top <= bottom && left <= right) {// 从左向右填充当前上边界所在行for (int i = left; i <= right; i++) {matrix[top][i] = num++;}// 上边界向下移动top++;// 从上到下填充当前右边界所在列for (int i = top; i <= bottom; i++) {matrix[i][right] = num++;}// 右边界向左移动right--;// 确保当前下边界在上边界下方，然后从右向左填充当前下边界所在行（如果是m*n的矩阵，这个不能少）if (top <= bottom) {for (int i = right; i >= left; i--) {matrix[bottom][i] = num++;}// 下边界向上移动bottom--;}// 确保当前左边界在右边界左方，然后从下到上填充当前左边界所在列if (left <= right) {for (int i = bottom; i >= top; i--) {matrix[i][left] = num++;}// 左边界向右移动left++;}}// 返回填充好的矩阵return matrix;
}

拓展

类似螺旋矩阵题的核心思路是利用边界变量来逐步收缩图形的边界。解题步骤如下：

1. 初始化边界；
2. 按要求进行模拟，最外层的while循环 控制边界收缩的范围，里面的for循环和边界变量的加加减减 模拟收缩过程 ；
3. 边界控制，如果是m*n的矩阵还要注意边界变量的变化不能超出边界收缩的范围。