代码随想录算法训练营第二天| 209.长度最小的子数组

209.长度最小的子数组

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

思路： 定义f（n）表示数组前n项的和

则寻找满足条件的f（n+k）-f(n)=val的k ，然后返回最小值的k

第一次解答：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {vector<int>sums(nums.size(),0);int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];sums[i]=sum;}for(int k=0;k<nums.size();k++){for(int n=0;n<sums.size()-k;n++){if((sums[n+k]-sums[n])==target){return k;}}}return 0;}};

错误地方：求的是子数组，而不是最小的连续子数组。

这里又是我看错了 求的确实是连续子数组 ，但是要求子数组值大于或等于目标值，而不是等于

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {vector<int>sums(nums.size()+1,0);int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];sums[i+1]=sum;       //这里+1的原因是让sums[0]=0;}for(int k=1;k<nums.size()+1;k++){for(int n=0;n<sums.size()-k;n++){if((sums[n+k]-sums[n])>=target){return k;}}}return 0;}};

这也是暴力解法，最终运行超时。

正确解法：

采用滑动窗口，窗口的终点不断往后滑，每当当前窗口的值超过或等于target时，就把窗口前端也尝试往前滑。

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

     思路：

按圈来考虑

每圈都会经过从左到右 从上到下 从右到左 从下到上的顺序

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>>ans(n, vector<int>(n, 0));int number = 1;int x = 0;int y = 0;for (int i = n; i >= 1; i = i - 2) {//左到右for (int j = 0; j < i; j++) {ans[x ][y++] = number++;}y--;x++;if (i == 1)break;//上到下for (int j = 0; j < i - 1; j++) {ans[x++][y] = number++;}x--;y--;//右到左for (int j = 0; j < i - 1; j++) {ans[x][y--] = number++;}x--;y++;if (i == 2)break;//下到上for (int j = 0; j < i - 2; j++) {ans[x--][y] = number++;}x++;y++;}return ans;}
};