刷题3道：977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ***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
自己写的暴力解法：先求平方，再用冒泡排序，时间复杂度O(n^2),通过132/137个测试用例，超出时间限制，没有通过。用快排应该可以通过。
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { for(int i=0;i<nums.size();i++){ nums[i] = nums[i] * nums[i]; }for(int m=0;m<nums.size()-1;m++){ for(int n=0;n<nums.size()-1-m;n++){ if(nums[n]>nums[n+1]){ int temp = nums[n]; nums[n] = nums[n+1]; nums[n+1] = temp; } } }
return nums; } }; 双指针法：复杂度O（n）,数组其实是有序的， 只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法. class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> result(nums.size(),0); int k = nums.size()-1; for(int i=0,j=nums.size()-1;i<=j;){ if(nums[i]*nums[i]>nums[j]*nums[j]){ result[k--]=nums[i]*nums[i]; i++; } else{ result[k--]=nums[j]*nums[j]; j--; } } return result; } }; ***209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
这道题没太看懂，完全没思路，后来看了题解才懂，需要多复习。
先说暴力解法，双层for循环，通过18/20个用例，超出时间范围，不行。
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int result = 10000000; int sublength; for(int i=0;i<nums.size();i++){ int sum=0; for(int j=i;j<nums.size();j++){ sum += nums[j]; if(sum>=target){ sublength = j-i+1; result = result > sublength ? sublength:result; break; } } } if(result == 10000000){ return 0; } else{ return result; } } }; 滑动窗口法：今天新学到的！ 所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。 在本题中实现滑动窗口，主要确定如下三点：窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
我的碎碎念：就是用一个滑动窗口，先从前往后确定个数和sum的值，再从前往后依次删除一个，直到滑动窗口满足条件且包含个数最少。
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int result = INT32_MAX; int sublength; int i=0; int sum=0; for(int j=0;j<nums.size();j++){ sum+=nums[j]; while(sum>=target){ sublength=j-i+1; result = result > sublength ? sublength : result; sum -= nums[i++]; } } return result == INT32_MAX ? 0 : result; } };疑问：滑动窗口的这个while循环不占时间复杂度的吗，它不是和for循环构成了嵌套吗，有没有可能这个while里也要执行好多次？
解答：不会，别绕进去，跳出来，每个元素 只有 进窗口一次，和出窗口一次，一个元素 就被操作两次，While里忽略不计。
***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/
我的碎碎念：这边界条件也太多了吧。确定圈数，确定区间，上下左右四个区间要一致，统一选左开右闭，要有坐标的概念，因为是2维，要确定位置，最后：
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去就ok了，今日任务完成，散会！
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n,vector<int>(n,0)); int startx=0; int starty=0; int offset=1; int loop=n/2; int mid=n/2; int count=1; int i,j; while(loop--){ for(j=starty;j<n-offset;j++){ res[startx][j]=count++; } for(i=startx;i<n-offset;i++){ res[i][j]=count++; } for(;j>starty;j--){ res[i][j]=count++; } for(;i>startx;i--){ res[i][j]=count++; } startx++; starty++; offset++; } if(n%2==1){ res[mid][mid]=n*n; } return res; } }; 标签：窗口,nums,int,训练营,随想录,算法,vector,result,https From： https://www.cnblogs.com/zzw0612/p/17011773.html