算法训练营day2|leetcode209.长度最小的子数组，59.螺旋矩阵 区间和 数组总结

1.leetcode长度最小的子数组https://leetcode.cn/problems/minimum-size-subarray-sum/第一想法滑动窗口一个快指针一个慢指针一开始fastslow然后fast开始走并记录fast到slow的长度总和如果长度总和大于target,slow如果等于target记录是不是最小的子数组如果是返回如果不是slow如果小于target,fast当时考虑的问题for循环里面是slow还是fast看完视频后for循环是fast*很重要优化当子数组的和等于target时不能立即返回因为后面可能存在更短的子数组应该是记录当前长度并与已记录的最小长度比较然后继续移动慢指针class Solution { public: int minSubArrayLen(int target, vectorint nums) { /*滑动窗口一个快指针一个慢指针一开始fastslow然后fast开始走并记录 fast到slow的长度总和,如果长度总和大于targetslow如果等于target记录是不是最小的 子数组如果是返回如果不是slow如果小于targetfast*/ //问题1for循环里面是slow还是fast /*看完视频后for循环是fast 当子数组的和等于target时不能立即返回因为后面可能存在更短的子数组 应该是记录当前长度并与已记录的最小长度比较然后继续移动慢指针 */ int slow0; int fast0; int sum0;//滑动窗口数值和 int resultINT32_MAX; int subL0;//滑动窗口的长度 for(fast0;fastnums.size();fast) { sumsumnums[fast]; while(sumtarget) { subL(fast-slow1);//取子序列的长度 if(resultsubL) { resultsubL; } else { resultresult; } sumsum-nums[slow];//精髓所在不断的变更起始位置 slow; } } if (result INT32_MAX) { return 0; // 没有找到符合条件的子数组 } else { return result; // 找到了返回最小长度 } } };2.leetcode59.螺旋矩阵https://leetcode.cn/problems/spiral-matrix-ii/第一想法没什么思路看卡哥的视频感觉有点乱去看了题解特别清晰思路从左到右从上到下从右到左从上到下依次打印打印完了就删除删除的方式就是改变边界条件1.定义上下左右边界2.依次移动到最右此时最上面的已经打印完成可以删除删除就是重新定义上边界3.判断若重新定义后上下边界交错则打印完成跳出循环返回答案4若不交错继续遍历向下向左向上操作同理5.反复循环直到边界交错跳出循环返回答案class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { //开始没什么思路 //看了题解特别清晰从左到右从上到下从右到左从下到上依次打印 int left0; int rightmatrix[0].size()-1; int top0; int bottommatrix.size()-1; vectorint res; if(matrix.empty()) return {}; while(leftrighttopbottom) { for(int ileft;iright;i)//从左到右 { res.push_back(matrix[top][i]); } top; if(topbottom) break; for(int itop;ibottom;i)//从上到下 { res.push_back(matrix[i][right]); } right--; if(rightleft) break; for(int iright;ileft;i--)//从右到左 { res.push_back(matrix[bottom][i]); } bottom--; if(topbottom) break; for(int ibottom;itop;i--)//从下到上 { res.push_back(matrix[i][left]); } left; if(rightleft) break; } return res; } };3.区间和https://kamacoder.com/problempage.php?pid1070第一想法暴力解法即定义一个新数组存入数组进行求和//定义一个数组array[n] //将数存入array //定义两个指针左指针和右指针 //sumarray[left]array[right] //cout sum; //输入输出的模式方法 #include iostream #include vector using namespace std; int main() { int n0; int left0; int right0; cinn; vectorint vec(n); for(int i0;in;i) { cinvec[i]; } while(cinleftright) { int sum0; for (int i left; i right; i) sum sumvec[i]; cout sum endl; } return 0; }但是这样会超时优化引入前缀和重复利用计算过的子数组和从而从而降低区间查询需要累加计算的次数有时候分不清前缀和的区间时建议多画画图模拟一下过程#include iostream #include vector using namespace std; int main() { int n0; int sum0; int a0; int b0; cinn; vectorint vec(n); vectorint res; for(int i0;in;i) { cinvec[i]; sumsumvec[i]; res.push_back(sum); } while(cinab) { int result0; if(a0) { resultres[b]; } else { resultres[b]-res[a-1]; } coutresultendl; } return 0; }数组总结