Day2

Day2

977.有序数组的平方

题目建议： 本题关键在于理解双指针思想

暴力解法:先平方 ，后排序。

双指针法

左负数，中间接近零，右正数，平方后两边大中间小

左右2个指针从头开始，互相比大小，谁更大就把值赋给新的数组，再向中间移动一格，注意从数组的最大下标开始赋值以满足非递减。

注意i<=j否则最后一个元素无法赋值到新数组中

209.长度最小的子数组

滑动窗口，也是双指针的一种

值大于s，比较长度后左端就要向右移动缩小窗口

将开始的返回值设置为INT32_MAX,是int类型中最大的值

for里面套while，每次右端向右移动单位一，如果满足>=s，左端持续向右移动直到sum<s,之后进行下一次for循环，右端向右移动一。

如果一直移动，直到整个数组的和都无法大于s，则返回0，说明没有这样的子序列

其中2次使用" ? : "结构简化代码

时间复杂度：尽管for套了while，但是每个元素进出共2次，2*n 所以是O

(n)。

59.螺旋矩阵II

题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。

坚持循环不变量原则

如图，区间左开右闭

vector<vector<int>> res(n, vector<int>(n, 0)); 
 // 使用vector定义一个二维数组
 
  j < n - offset;
 // offset 控制每一圈里每一条边遍历的长度
   offset += 1;

注意n为奇数时最中间元素需要单独处理，赋值count

别忘了开始int middle的用意