977. 有序数组平方
1.暴力解法（平方后进行排序即可）
public int[] sortedSquares(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
ans[i] = nums[i] * nums[i];
}
Arrays.sort(ans);
return ans;
}
2.双指针方法（第一种）
- 所有数都是非负数，那么将每个数平方后，数组仍然保持升序；所有数都是负数，那么将每个数平方后，数组会保持降序。
- 找到数组中负数与非负数的分界线，分界线左边单调递减，分界线右边单调递增。
- 两个已经有序的子数组用归并的方法进行排序。
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
//neg正负分界线的位置
int neg = -1;
for (int i = 0; i < n; i++) {
if (nums[i] < 0) {
neg = i;
} else {
break;
}
}
int index = 0;
//i为分界线位置
int i = neg;
//j为分界线右边+1位置
int j = neg + 1;
while (i >= 0 || j < n) {
if (i < 0) { //i小于0，说明数组不存在负数，j的初始值为-1+1=0
ans[index] = nums[j] * nums[j];
j++;
} else if (j == n) {//j等于n，说明数组只有负数，i的初始值为n-1
ans[index] = nums[i] * nums[i];
i--;
} else if (nums[i] * nums[i] < nums[j] * nums[j]) {
//负数和非负数都有，i单调递减
ans[index] = nums[i] * nums[i];
i--;
} else {
//负数和非负数都有，j单调递增
ans[index] = nums[j] * nums[j];
j++;
}
index++;
}
return ans;
}
}
3.双指针方法（第二种）
- 左指针 0?和右指针 n?1，比较左右指针的数，选择较大的那个逆序放入答案并移动指针
?
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, k = n - 1; i <= j; ) {
if (nums[i] * nums[i] < nums[j] * nums[j]) {
ans[k] = nums[j] * nums[j];
j--;//j为右指针，向左走
} else {
ans[k] = nums[i] * nums[i];
i++;//i为左指针，向右走
}
k--;//逆序放入
}
return ans;
}
}
209. 长度最小子数组
滑动窗口：
本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动，如图所示：
?
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//滑动窗口解法
int sum = 0;
int ans = Integer.MAX_VALUE;
int left = 0;
//类似双指针，用右指针来确定窗口的走向，比target小，sum就一直加
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
//满足条件，记录最小的长度
while (sum >= target) {
ans = Math.min(ans, right - left + 1);
//减小窗口
sum -= nums[left++];
}
}
//ans为初始最大值，说明sum比target小，返回0
if (ans == Integer.MAX_VALUE) {
return 0;
}
return ans;
}
}59. 螺旋矩阵
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
?
- 这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
- 这也是坚持了每条边左闭右开的原则。
?
class Solution {
public int[][] generateMatrix(int n) {
int[][] ans = new int[n][n];
int startX = 0, loop = 0, count = 1;
int i, j;
while (loop++ < n / 2) {
//上方：从左到右（左闭右开），不包含最后一个值
for (j = startX; j < n - loop; j++) {
ans[startX][j] = count++;
}
//右方：从上到下（左闭右开），不包含最后一个值
for (i = startX; i < n - loop; i++) {
ans[i][j] = count++;
}
//下方：从右到左（左闭右开），不包含最后一个值
for (; j >= loop; j--) {
ans[i][j] = count++;
}
//左方：从下到上（左闭右开），不包含最后一个值
for (; i >= loop; i--) {
ans[i][j] = count++;
}
startX++;
}
if (n % 2 == 1) {
ans[startX][startX] = count;
}
return ans;
}
}