day02-数组part02
一、长度最小的子数组（滑动窗口）
leetcode 209 长度最小子数组
这道题的核心思想就是使用滑动窗口，滑动窗口三板斧：
- 初始位置i
- 滑动窗口长度j-i+1
- 结束位置j
我们在写代码时是通过for循环来控制结束位置j，而初始位置i是在满足条件的情况下才向前移动的
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i=0,j=0;//i是窗口起始位置，j是终止位置int result = INT32_MAX; //因为要找到最小的，如果初始成0，那0永远是最小的int subLength = 0; //子数组长度int sum = 0;for(j=0;j<nums.size();j++){sum += nums[j]; //一直叠加到终止位置while(sum >= target){ //满足条件后要判断此时字串长度是否更小，同时移动起始位置isubLength = j-i+1;if(subLength < result) result = subLength;sum -= nums[i];//i指针移动，sum减去一个值i++;}}return result==INT32_MAX ? 0:result;}
};二、模拟 - 螺旋矩阵Ⅱ
leetcode 59 螺旋矩阵
这道题目就是要模拟按照顺时针画矩阵的过程
- 填充上行从左到右
- 填充右列从上到右
- 填充下列从右到左
- 填充左列从下到上
同时需要注意的是每一行（列）的处理范围要保持一致——左闭右开
我们首先要确定总共要绕多少圈（loop）,接着就在每一圈内顺时针填充行列，一定要注意边界处理条件
class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> result(n,vector<int>(n,0));int loop = n/2; //所要走的圈数int startx = 0,starty = 0; //每一圈开始的起始位置int mid = n/2; //中间值（在n为奇数时需要特殊处理）int offset = 1; //用于处理每一圈的边界int i,j;int count = 1;//向矩阵中填的数while(loop){i = startx;j = starty;//四个for循环模拟for(j;j<n-offset;j++){ //模拟上行从左到右result[i][j] = count;count++;}for(i;i<n-offset;i++){//模拟右列从上到下result[i][j] = count++;}for(j;j>starty;j--){//模拟下行从右到左（注意边界条件，同时这里循环变量刚好从上面结束的j开始）result[i][j] = count++;}for(i;i>startx;i--){//模拟左列从下到上result[i][j] = count++;}startx++;starty++;offset++; //表示边界的结束位置要少一位（因为下一处绕的圈变小了）loop--;}//处理n是边界的情况if(n%2 != 0){result[mid][mid] = count;}return result;}
};三、一维前缀和
题目
前缀和用来求解区间之和，一维指的是求解的是一维数组的前缀和。
前缀和的核心思想就是设置了一个前缀和数组sum
sum数组初始化如下：
- sum[0] = Array[0]
- i>0,sum[i] = sum[i-1] + Array[i]
接下来就可以利用sum数组来求解数组区间[a,b]的和，利用下面的公式计算：
- 当a = 0 时 ， result = sum[b]
- 当a>0时，result = sum[b] - sum[a-1]
#include<bits/stdc++.h>
using namespace std;int main(){int n,i;int a,b;int result;cin>>n;vector<int>Array(n);vector<int>sum(n,0);for(i=0;i<n;i++){cin>>Array[i];}sum[0] = Array[0];for(i=1;i<n;i++){sum[i] = sum[i-1] + Array[i];}while(cin>>a>>b){if(a==0) result = sum[b];else result = sum[b] - sum[a-1]; printf("%d\n",result);}
}