977. 有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
做题思路
由于原数组存在负数，所以平方后最大值可能出现在两端。因此可以采用双指针法，在数组首尾各放置一个指针，比较指针元素平方后的值。较大者放入结果数组末端，同时该指针向中间移动，继续比较。
参考代码
class Solution {
public int[] sortedSquares(int[] nums) {
int left=0;//左指针
int right=nums.length-1;//右指针
int[] result=new int[nums.length];//结果数组
int index=result.length-1;//结果数组的指针要放在末端
while(left<=right){//注意等号
if(nums[left]*nums[left]>nums[right]*nums[right]){//左指针元素平方比右指针大
result[index--]=nums[left]*nums[left];//左指针元素平方放入结果数组
++left;//左指针移动
}
else{
result[index--]=nums[right]*nums[right];//右指针元素平方放入结果数组
--right;//右指针移动
}
}
return result;
}
}
209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
做题思路
由于本题的目标是连续子数组，所以可以想到使用滑动窗口法，也就是双指针法。
将右指针设定为子数组的右端，左指针为左端。首先左指针不动，右指针右移，滑动窗口不断增长，和不断增加，当和 ≥ target 时，此时的长度满足条件，但题目要求长度最小，因此需要与之前成立的长度进行比较，更新最小长度。同时左指针右移，更新滑动窗口。
参考代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left=0;//左指针
int result=Integer.MAX_VALUE;
int sum=0;
for(int right=0;right<nums.length;right++){//左指针不动，右指针右移，构建窗口
sum+=nums[right];
while(sum>=target){//此时窗口内的和已经满足条件
result=Math.min(result,right-left+1);//更新最小长度
sum-=nums[left++];//左指针右移，开始新一轮窗口
}
}
return result==Integer.MAX_VALUE?0:result;
}
}
59. 螺旋矩阵 II
题目描述
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
做题思路
本题的关键点是区间左右的开闭和n 奇偶的分别处理，将一圈分为上下左右 4 个左开右闭的区间。
参考代码
//采取左闭右开区间
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++<n/2){//注意没有等号，因为第1圈是第0次循环
for(j=start;j<n-loop;j++){
res[start][j]=count++;//上面从左到右
}
for(i=start;i<n-loop;i++){
res[i][j]=count++;//右边从上到下
}
for(;j>=loop;j--){
res[i][j]=count++;//下面从右到左
}
for(;i>=loop;i--){
res[i][j]=count++;//左边从下到上
}
start++;
}
if(n%2==1){//如果n是奇数，中心要单独赋值
res[n/2][n/2]=count;
}
return res;
}
}
