977.有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
算法思想：
简单的方法：平方之后，快速排序
更近一步的方法：用空间换时间。
可以发现，平方之后的数据有个特点，最大的数分布在两头，此时可以用头尾指针从前后开始比较，找到一个大的，放到新定义的数组末尾，知道两个指针相遇就结束。
代码：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
//要求是O(n)的时间复杂度的时候，可以想到用双指针法
int len = nums.size();
int left =0;
int right = len-1;
vector<int> copy(len, 0);
int i = len;
while(left<=right)
{
// cout<<"i:"<<i << " right:"<<right<<" left:"<<left;
int r_sqr = nums[right] * nums[right];
int l_sqr = nums[left] * nums[left];
// cout<<"i:"<<i << " right:"<<right<<" left:"<<left<<"r_sqr"<<r_sqr<<"l_sqr"<<l_sqr;
if(r_sqr > l_sqr)
{
copy[--i] = r_sqr;
right--;
}
else
{
copy[--i] = l_sqr;
left++;
}
cout<<" copy:"<<copy[i]<<endl;
}
return copy;
}
};
209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
算法思想：滑动窗口
思路：
用一个快慢指针指向窗口的头尾，要明确快慢指针是用开区间还是闭区间。快指针找到一个区间，满足区间和大于target，此时慢指针可以往前移动，找到一个最短的区间。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//操作数组，可以想到用双指针的方法，其实双指针本质上是两个for循环的浓缩
int len = nums.size();
int fast = 1;
int slow = 0;
int min_len = len+1;
int sum = nums[0];
while(fast <= len)
{
if(sum<target) //还不够，fast往上增加
{
if(fast>=len)
break;
sum += nums[fast];
fast++;
}
else
{
if(min_len>(fast-slow))
{
min_len = fast - slow;
}
sum -= nums[slow];
slow++;
}
}
if(min_len==(len+1))
return 0;
return min_len;
}
};
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
算法思想：循环不变量
思路：
需要遍历矩阵的上下左右四个方向，遍历的过程其实是重复性的过程，但是由于是在矩阵中，边界之间有重复，往往搞不清楚边界问题。只要我们把四个方向的遍历长度保持一致，即区间大小保持一致，就不容易弄乱。
如何定义?即定义左闭右开的区间，遍历的时候遍历起始节点而不遍历终止节点，因为终止节点要作为下一个遍历的起始节点。这样我们就能很容易的写出来4个for循环遍历完成一圈。
第二圈的时候，只是把遍历范围减小了，其他不变。
需要定义起始边界：startx, starty
终止边界：n-offset,n-offset
代码：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
//用双指针解决，j表示水平方向移动的指针，i表示竖直方向的指针
vector<vector<int>> nums(n, vector<int> (n, -1));
int startx = 0;
int starty= 0;
int k = 0;
int i= startx;
int j = starty;
int offset = 1;
int count = 1;
while(k<n/2)
{
i = startx;
j = starty;
for(;j<n-offset;j++)
{
nums[i][j] = count;
count++;
cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
}
for(;i<n-offset;i++)
{
nums[i][j] = count;
count++;
cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
}
for(;j>starty;j--)
{
nums[i][j] = count;
count++;
cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
}
for(;i>startx;i--)
{
nums[i][j] = count;
count++;
cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
}
// cout<<"end"<<endl;
offset++;
startx +=1;
starty +=1;
k++;
}
if(n%2==1)
{
nums[n/2][n/2] = count;
// cout<<"0:"<<nums[0][0];
}
// cout<<1/2<<endl;
return nums;
}
};
