行业知识
代码随想录算法(Java)| 977.有序数组的平方 、209.长度最小的子数组、59.螺旋矩阵II
977.有序数组的平方
题���链接：977.有序数组的平方
文档讲解：977.有序数组的平方
视频讲解：977.有序数组的平方
暴力排序
最直观的想法，莫过于：每个数平方之后，排个序
这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度
public class SortedSquares { public static int[] sortedSquares(int[] nums) { int n = nums.length; int[] result = new int[n]; for (int i = 0; i 双指针法
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i]
如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。
如动画所示：
此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。
class Solution { public int[] sortedSquares(int[] nums) { int right = nums.length - 1; int left = 0; int[] result = new int[nums.length]; int index = result.length - 1; while (left nums[right] * nums[right]) { // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置 result[index--] = nums[left] * nums[left]; ++left; } else { result[index--] = nums[right] * nums[right]; --right; } } return result; }}class Solution { public int[] sortedSquares(int[] nums) { int l = 0; int r = nums.length - 1; int[] res = new int[nums.length]; int j = nums.length - 1; while(l nums[r] * nums[r]){ res[j--] = nums[l] * nums[l++]; }else{ res[j--] = nums[r] * nums[r--]; } } return res; }} 209.长度最小的子数组
题目链接： 209.长度最小的子数组
文档讲解： 209.长度最小的子数组
视频讲解： 209.长度最小的子数组
暴力解法
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2)，空间复杂度：O(1)，力扣超时。
public static int minSubArrayLen(int target, int[] nums) { int n = nums.length; int minLength = Integer.MAX_VALUE;// 最终的结果 int subLength = 0; // 子序列的长度 for (int i = 0; i = target) { subLength = j - i + 1; // 取子序列的长度 minLength = minLength 滑动窗口
接下来就开始介绍数组操作中另一个重要的方法：滑动窗口。
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
那么问题来了， 滑动窗口的起始位置如何移动呢？
这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
最后找到 4，3 是最短距离。
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动，如图所示：
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
一些录友会疑惑为什么时间复杂度是O(n)：
不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。
class Solution { // 滑动窗口 public int minSubArrayLen(int s, int[] nums) { int left = 0; int sum = 0; int result = Integer.MAX_VALUE; for (int right = 0; right = s) { result = Math.min(result, right - left + 1); sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; }}59.螺旋矩阵II
题目链接： 59.螺旋矩阵II
文档讲解： 59.螺旋矩阵II
视频讲解：59.螺旋矩阵II
思路
求解本题依然是要坚持二分法的循环不变量原则。
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
那么我按照左闭右开的原则，来画一圈，大家看一下：
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
这也是坚持了每条边左闭右开的原则。
一些同学做这道题目之所以一直写不好，代码越写越乱。
就是因为在画每一条边的时候，一会左开右闭，一会左闭右闭，一会又来左闭右开，岂能不乱。
- 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
- 空间复杂度 O(1)
class Solution { public int[][] generateMatrix(int n) { int loop = 0; // 控制循环次数 int[][] res = new int[n][n]; int start = 0; // 每次循环的开始点(start, start) int count = 1; // 定义填充数字 int i, j; while (loop++ = loop; j--) { res[i][j] = count++; } // 模拟左侧从下到上 for (; i >= loop; i--) { res[i][j] = count++; } start++; } if (n % 2 == 1) { res[start][start] = count; } return res; }}
