题目：997.有序数组的平方

Leetcode原题链接：997.有序数组的平方——力扣

思考历程与知识点：

题目的意思很简单，就是把每个数的平方，按从小到大的顺序排个序，再输出出来。

第一想法是先每个数平方一遍，用sort（）函数排序一步到位。但是这道题用sort时间复杂度很高，主要考查的是对双指针的理解，所以两种方法都做一遍吧。

为什么选用双指针做法：因为原来的数组是有序的，并且可以有负数，所以平方之后最大值要么在最左边，要么在最右边，在左右两端放两个指针，依次比较排序，就可以得到排好的数组啦

题解：

1、用 sort() 一步到位法：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> res;for(int i : nums) res.push_back(i * i);sort(res.begin(),res.end());return res;}
};

2、双指针法

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> res;int l = 0, r = nums.size()-1;while(r >= l){if(nums[l] * nums[l] >= nums[r] * nums[r]) {res.push_back(nums[l]*nums[l]);l++;}else {res.push_back(nums[r]*nums[r]);r--;}}reverse(res.begin(),res.end());return res;}
};

题目：209. 长度最小的子数组

Leetcode原题链接：力扣

思考历程与知识点：

题目最后一句的进阶，相当于是提示有O（n）的解法，也有O（n log(n)）的解法。

但是，O（n）复杂度是小的那个，进阶反而要设计一个复杂度更大的，一般都应该反着来的，复杂度越小越好啊。所以题目是想引导我们思考别的解题方式。

那就先想想O（n）。第一反应，前缀和。想了想，确实就是O（n）的解法。

至于O（n log(n)），其实是滑动窗口，就像一只毛毛虫，从这个长长的数组上爬过去，身子下面的数字和如果小了，那其他位置不动，就头往前探探，多加几个数字，如果大了，那尾巴就收回来一点，少加几个数字。根据这个原则，毛毛虫爬完一趟，就知道最短的区间长度是多少了。（奇妙の比喻hhh）

题解：

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int l = 0, r = 0,sum = nums[0];int len = INT_MAX;while( 1) {if(sum < s && r+1 < nums.size()) {r++;sum=sum + nums[r];}else if(sum >= s){if(len > r - l + 1)len = r - l + 1;sum=sum - nums[l++];}else{break;}}if(len == INT_MAX)len = 0;return len;}
};