977.有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文档讲解：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
视频讲解：https://www.bilibili.com/video/BV1QB4y1D7ep
思路
- 双指针。重新定义一个数组res，让指针指向最后，因为两端的数平方之后会最大，然后双指针一头一尾向中间靠拢。
代码
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int left = 0, right = nums.length - 1, k = nums.length - 1;
while(left <= right){
if (nums[left] * nums[left] >= nums[right] * nums[right]) {
res[k--] = nums[left] * nums[left];
left++;
} else {
res[k--] = nums[right] * nums[right];
right--;
}
}
return res;
}
}
分析：
时间复杂度：O(n)，空间复杂度：O(1)。
总结
刚开始自己想的时候只想到了暴力排序。而这道题是有序数组，最大的数不在最左边就在最右边，所以可以考虑双指针从两侧向中间逼近。
209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文档讲解：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
视频讲解：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
思路
- 滑动窗口。定义两个指针都指向头结点，边移动边计算是否等于target，如果大于target，就记录长度，并把两个指针都指向下一个结点。
代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while(sum >= target) {
int len = right - left + 1;
minLen = Math.min(minLen, len);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
分析：
时间复杂度：O(n)，空间复杂度：O(1)。
不是for里面包含while时间复杂度就是O(n^2)，而是要看元素被操作的次数。每一个元素进入滑动窗口操作一次，出滑动窗口操作一次，一共是两次，所以时间复杂度是O(2 * n)，也就是O(n)。
59.螺旋矩阵II
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文档讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
思路
- 捋清转圈逻辑，区间定义
代码
int[][] nums = new int[n][n];
int startX = 0, startY = 0;
int offset = 1;
int count = 1;
int loop = 1;
int i, j;
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++;
}
startX++;
startY++;
offset++;
loop++;
}
if (n % 2 == 1) {
nums[startX][startY] = count;
}
return nums;
分析：
时间复杂度：O(n^2)，空间复杂度：O(1)。
数组专题总结
数组是存放在连续内存空间上的相同类型数据的集合。但二维数组的存放空间不连续，是以行为连续的空间。
二分法
应用于有序数组的查询。用nums[middle]与target进行比较，来改变left和right的值。需要注意左闭右开和左闭右闭的区间处理。
双指针—快慢指针
应用于移除数组元素。需要注意数组中的元素不能被删除，只能被覆盖。快指针负责遍历数组，慢指针负责存放符合条件的元素。
双指针
应用于对有序数组的平方排序。定义一个新的数组res，比较left指针和right指针指向的数的平方，从res的最后一位进行赋值，因为两头的数平方最大。
滑动窗口
应用于获取符合总和大于等于target子数组的最小长度。先移动right，当数组和大于等于target后，开始移动left依次减小数组，直到小于target，然后left保持不动，再移动right。
需要注意虽然这里是for中包含while，但时间复杂度是O(n)。
螺旋矩阵
寻找规律以及注意区间的问题。
