代码随想录算法训练营第2天 | 209.长度最小的子数组、59.螺旋矩阵II、区间和、开发商购买土地209.长度最小的子数组题目描述解题思路解题过程59.螺旋矩阵II题目描述解题思路解题过程区间和前缀和题目描述解题思路解题过程开发商购买土地题目描述解题思路解题过程209.长度最小的子数组题目链接209.长度最小的子数组题目描述解题思路这是一道滑动窗口的题目。滑动窗口就是不断调节子序列中的起始位置和结束位置得到需要的结果。可以使用双指针达到需求。一个指针作为结束位置一个指针是起始位置在循环中首先通过叠加如果超过了目标值即记录当前长度然后将起始指针向前移动将最开始的那个值给移除。解题过程classSolution{public:intminSubArrayLen(inttarget,vectorintnums){intresultINT_MAX;intsum0;// 记录前几个数的总和intlength0;// 记录子数组长度inti0;intj0;for(j0;jnums.size();j){sumnums[j];while(sumtarget){lengthj-i1;resultresultlength?result:length;sum-nums[i];}}returnresultINT_MAX?0:result;}};59.螺旋矩阵II题目链接59.螺旋矩阵II题目描述解题思路这题主要是想象模拟的过程模拟顺时针画矩阵的过程。关键点在于处理边界问题我们需要想象怎么处理矩阵的四条边卡哥提到左闭右开的办法即每一条边的循环只遍历到最后一个点的前一位然后把最后一个点交给下一条边的遍历。解题过程classSolution{public:vectorvectorintgenerateMatrix(intn){vectorvectorintnums(n,vectorint(n,0));intstx0,sty0;intoffset1;// 边界intcount1;// 元素赋值intloopn/2;// 循环次数intmidn/2;// 只为n是奇数对中间值赋值inti,j;while(loop--){istx;jsty;for(j;jn-offset;j)nums[stx][j]count;for(i;in-offset;i)nums[i][j]count;for(;jsty;j--)nums[i][j]count;for(;istx;i--)nums[i][j]count;stx;sty;offset;// 将循环的矩阵初始点提升相对的边界也得跟着提升这样才能在边的后面多减少}if(n%2){nums[mid][mid]count;}returnnums;}};区间和前缀和题目链接区间和题目描述解题思路典型的前缀和题目直接套公式前缀和的初始化s[n] s[n-1[ a[n]; 区间和a b即S s[b] - s[a-1];解题过程#includeiostreamusingnamespacestd;constintN100010;intn;inta[N],s[N];intc,b;intmain(){scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);}for(inti1;in;i){s[i]s[i-1]a[i];}while(cincb){if(c0)printf(%d\n,s[b1]);elseprintf(%d\n,s[b1]-s[c]);}return0;}开发商购买土地题目链接开发商购买土地题目描述解题思路涉及二维数组的前缀和代码随想录里面的代码我没咋看明白感觉比较复杂我使用的是y总的思路。首先也是套公式二维数组前缀和公式s[ i ][ j ] s[ i - 1 ][ j ] s[ i ][ j - 1 ] - s[ i - 1 ][ j - 1 ] a[ i ][ j ]二维数组区间的值S s[ x2 ][ y2 ] - s[ x1 - 1 ][ y2 ] - s[ x2 ][ y1 - 1] s[x1 - 1] [ y1 - 1 ]这道题他的土地划分是简单的一道切所以当得到了二维数组的前缀和之后就可以直接循环每一列和每一行将总和减掉这一行切掉的值再加上由于是比较差值所以减掉一次是另一半的和那么减掉两次就是差值了所以使用绝对值函数abs来判断差值大小。解题过程#includeiostream#includestdlib.h#includeclimitsusingnamespacestd;constintN110;intn,m;inta[N][N],s[N][N];intmin(intx,inty){returnxy?x:y;}intmain(){scanf(%d%d,n,m);for(inti1;in;i){for(intj1;jm;j){scanf(%d,a[i][j]);}}for(inti1;in;i){for(intj1;jm;j){s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}}intansINT_MAX;for(inti1;in;i){intxabs(s[n][m]-2*s[i][m]);ansmin(ans,x);}for(intj1;jm;j){intxabs(s[n][m]-2*s[n][j]);ansmin(ans,x);}printf(%d,ans);return0;}