代码随想录-DAY②-数组——leetcode 977 | 209

977

思路

使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。

时间复杂度：O(n)
空间复杂度：O(1)

代码

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int left = 0;int right = nums.size()-1;int last = right;vector<int> ans(nums.size());while(left<=right){if(nums[left]*nums[left]>nums[right]*nums[right]){ans[last--]=nums[left]*nums[left++];}else{ans[last--]=nums[right]*nums[right--];}}return ans;}
};

209

思路

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

时间复杂度：O(n)
空间复杂度：O(1)

代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, sublen = 0, i=0;int result = INT32_MAX;for (int j=0; j<nums.size(); j++){sum+=nums[j];while(sum>=target){sublen = j-i+1;result = sublen<result?sublen:result;sum -= nums[i++];}}return result == INT32_MAX?0:result;}
};