一、977. 有序数组的平方
学习链接：有序数组的平方
状态：暴力解法与双指针都做出来了
时间复杂度：暴力解法 O(
) 双指针解法 O(
)
细节之处：暴力解法 1 双指针解法 1
暴力解法
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i=0;i<nums.length;i++)
{
nums[i]*=nums[i];
}
for(int i=0;i<nums.length-1;i++) //1 最后一个不需要排序
{
for(int j=i+1;j<nums.length;j++)
{
if(nums[i]>=nums[j]) {
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
}
return nums;
}
}双指针解法
class Solution {
public int[] sortedSquares(int[] nums) {
int[] make_nums=new int[nums.length];
int point= nums.length-1;
int left=0;int right= nums.length-1;
while(left<=right) //1 注意这里只能左闭右闭，只有这样最后一个元素才是有意义的
{
if(nums[left]*nums[left]>nums[right]*nums[right]) {
make_nums[point--] = nums[left]*nums[left];
left++;
}
else{
make_nums[point--]=nums[right]*nums[right];
right--;
}
}
return make_nums;
}
}暴力解法的思路：先平方再排序，没练过，只能写出排序 O() ，后续会提高的。
双指针解法的思路：因为是有序数组，所以首部和尾部的绝对值是最高的，自然平方也是最大的，每次这样比较，确定最大元素放入新的平方后的有序数组。
二、209. 长度最小的子数组
学习链接：长度最小的子数组
状态：暴力解法超时了，双指针没想出来
时间复杂度：暴力解法 O(
细节之处：暴力解法 1 2 双指针解法 1 2
暴力解法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int total=Integer.MAX_VALUE;
for(int i=0;i<nums.length-1;i++)
{
int sum=nums[i];
int cnt=1;
if(sum>=target)return cnt; //1 注意如果第一个数字就大于的target的情况
for(int j=i+1;j<nums.length;j++)
{
sum+=nums[j];
cnt++;
if(sum>=target)
{
if(cnt<total)
{
total=cnt;
}
break;
}
}
}
if(nums[nums.length-1]>=target)return 1; //2 上述没有对最后一个元素大于target的情况
if(total!=Integer.MAX_VALUE)
return total;
else return 0;
}
}双指针解法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i=0;
int sum=0;
int result=Integer.MAX_VALUE;
for(int j=0;j<nums.length;j++)
{
sum+= nums[j];
while (sum>=target)
{
result=Math.min(result,j-i+1);
sum-=nums[i]; //1 模拟首指针加一，更新序列和
i++; //2 首指针后移
}
}
return result==Integer.MAX_VALUE?0:result;
}
}暴力解法的思路：利用双层循环，考虑每一组首尾元素的情况，确定所有序列的情况来更新最小数组长度
双指针解法思路：遍历每个元素都当作数组的尾元素，因为序列和是连续数组的和，所以滑动窗口去掉了冗余序列，只关注大于target的数组长度。
三、59螺旋矩阵II
学习链接：螺旋矩阵Ⅱ
状态：没做出来
时间复杂度：O(
细节之处：1 2 3 4 5
class Solution {
public int[][] generateMatrix(int n) {
int loop=1;
int startx=0,starty=0,offset=1;
int arr[][]=new int[n][n];
int i=0,j=0,count=1;
while(loop<=n/2) //1 每圈有左右俩列，所以n/2，奇数还会多一个元素，最后判断
{
for(j=starty;j<n-offset;j++) //2 列的终点因转了几圈而改变
{
arr[startx][j]=count++;
}
for(i=startx;i<n-offset;i++) //3 列的终点因转了几圈而改变
{
arr[i][j]=count++;
}
for(;j>starty;j--)
{
arr[i][j]=count++;
}
for(;i>startx;i--)
{
arr[i][j]=count++;
}
startx++;starty++;offset++;loop++; //4 每圈转完之后需要更新起点和行列的参数
}
if(n%2==1)
{
arr[startx][starty]=count;//5 多出来的最后一个元素便是下一个起点
}
return arr;
}
}思路： 这道题是一个模拟题，围绕起点进行的转圈模拟，关键是要遵守循环不变量原则，即上下左右每次处理的量是一样的。
四、 数组总结
标签：59,target,nums,int,随想录,数组,解法,指针 From： https://blog.csdn.net/www_www10/article/details/140522731学习链接：数组总结
个人心得：数组是算法的基础吧，基本每个题目都会涉及到数组，一定要特别关注数组的首尾元素的处理，这里面自己做题的出错率最高，