算法训练营day2|leetcode209.长度最小的子数组，59.螺旋矩阵 区间和 数组总结
1.leetcode长度最小的子数组：https://leetcode.cn/problems/minimum-size-subarray-sum/
第一想法：滑动窗口，一个快指针，一个慢指针，一开始fast=slow，然后fast开始走，并记录
fast到slow的长度总和，如果长度总和大于target,slow++，如果等于target，记录是不是最小的子数组，如果是，返回，如果不是，slow++，如果小于target,fast++
当时考虑的问题：for循环里面是slow还是fast
看完视频后：for循环是fast*很重要
优化：
当子数组的和等于target时，不能立即返回，因为后面可能存在更短的子数组，应该是记录当前长度，并与已记录的最小长度比较，然后继续移动慢指针
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { /*滑动窗口，一个快指针，一个慢指针，一开始fast=slow，然后fast开始走，并记录 fast到slow的长度总和,如果长度总和大于target，slow++，如果等于target，记录是不是最小的 子数组，如果是，返回，如果不是，slow++，如果小于target，fast++*/ //问题1：for循环里面是slow还是fast /*看完视频后：for循环是fast 当子数组的和等于target时，不能立即返回，因为后面可能存在更短的子数组 应该是记录当前长度，并与已记录的最小长度比较，然后继续移动慢指针 */ int slow=0; int fast=0; int sum=0;//滑动窗口数值和 int result=INT32_MAX; int subL=0;//滑动窗口的长度 for(fast=0;fast<nums.size();fast++) { sum=sum+nums[fast]; while(sum>=target) { subL=(fast-slow+1);//取子序列的长度 if(result>subL) { result=subL; } else { result=result; } sum=sum-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: vector<int> spiralOrder(vector<vector<int>>& matrix) { //开始没什么思路 //看了题解特别清晰，从左到右，从上到下，从右到左，从下到上依次打印 int left=0; int right=matrix[0].size()-1; int top=0; int bottom=matrix.size()-1; vector<int> res; if(matrix.empty()) return {}; while(left<=right&&top<=bottom) { for(int i=left;i<=right;i++)//从左到右 { res.push_back(matrix[top][i]); } top++; if(top>bottom) break; for(int i=top;i<=bottom;i++)//从上到下 { res.push_back(matrix[i][right]); } right--; if(right<left) break; for(int i=right;i>=left;i--)//从右到左 { res.push_back(matrix[bottom][i]); } bottom--; if(top>bottom) break; for(int i=bottom;i>=top;i--)//从下到上 { res.push_back(matrix[i][left]); } left++; if(right<left) break; } return res; } };3.区间和：https://kamacoder.com/problempage.php?pid=1070
第一想法：暴力解法，即定义一个新数组，存入数组，进行求和
//定义一个数组，array[n] //将数存入array //定义两个指针，左指针和右指针 //sum=array[left]+array[right] //cout << sum; //输入输出的模式方法 #include <iostream> #include <vector> using namespace std; int main() { int n=0; int left=0; int right=0; cin>>n; vector<int> vec(n); for(int i=0;i<n;i++) { cin>>vec[i]; } while(cin>>left>>right) { int sum=0; for (int i = left; i <= right; i++) sum =sum+vec[i]; cout << sum << endl; } return 0; }但是这样会超时
优化：引入前缀和，重复利用计算过的子数组和，从而从而降低区间查询需要累加计算的次数
有时候分不清前缀和的区间时，建议多画画图，模拟一下过程
#include <iostream> #include <vector> using namespace std; int main() { int n=0; int sum=0; int a=0; int b=0; cin>>n; vector<int> vec(n); vector<int> res; for(int i=0;i<n;i++) { cin>>vec[i]; sum=sum+vec[i]; res.push_back(sum); } while(cin>>a>>b) { int result=0; if(a==0) { result=res[b]; } else { result=res[b]-res[a-1]; } cout<<result<<endl; } return 0; }