长度最小的子数组
题目链接：[https://leetcode.cn/problems/minimum-size-subarray-sum/]
文章讲解：[https://programmercarl.com/0209.长度最小的子数组.html]
视频讲解：[https://www.bilibili.com/video/BV1tZ4y1q7XE]
解法
该题采用滑动窗口来解决。与暴力法的先固定起点再遍历终点再移动起点再遍历终点...不同，滑动窗口则是有一个前索引，一个后索引组成窗口，前索引向前滑动，判断窗口内的和是不是大于目标值，
如果小于：
- 窗口继续滑动，后索引向后，更新和。
如果大于等于： - 记录窗口长度，与目前的最大值比较；前索引向后，使窗口滑动（如果向前一个格子，和依然大于等于目标值，则继续滑动）
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i = 0;int sum = 0;int result = 1e9+ 1;int len;for(int j = 0;j < nums.size();j++){sum += nums[j];while(sum >= target){len = j - i + 1;result = result < len?result : len;sum = sum - nums[i];i++;}}if(result == 1e9 + 1) return 0;else return result;}
};
思考
滑动窗口适用于在数组中寻找符合要求的一段子序列，避免了窗口一端固定死的暴力穷举，而是让窗口滑动起来，让起点和终点在特定条件下移动。
螺旋矩阵
题目链接：[https://leetcode.cn/problems/spiral-matrix-ii/]
文章讲解：[https://programmercarl.com/0059.螺旋矩阵II.html]
视频讲解：[https://www.bilibili.com/video/BV1SL4y1N7mV/]
解法
使用方向数组，设置预选方向，之前做过很多次了
class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> matrix(n,vector<int>(n));int i = 0;int j = 0;vector<vector<int>> direction{{0,1},{1,0},{0,-1},{-1,0}};//right,down,left,upint dir = 0;int ni = i;int nj = j;vector<vector<int>> map(n,vector<int>(n,0));for(int m = 1;m <= n * n;m++){if(ni < 0 || ni >= n || nj < 0 || nj >= n || map[ni][nj] == 1){dir = (dir + 1) % 4;ni = i + direction[dir][0];nj = j + direction[dir][1];}i = ni;j = nj;matrix[i][j] = m;map[i][j] = 1;ni += direction[dir][0];nj += direction[dir][1];}return matrix;}
};
区间和
链接：[https://kamacoder.com/problempage.php?pid=1070]
解法
不使用暴力法，采用前缀和，即一个p数组，p[i]用于存储数据数组从arr[0] ~ arr[i]的值,这样从索引a到索引b的和不用重复计算，直接用p[b] - p[a - 1]即可。
#include<iostream>
#include<vector>
using namespace std;int main(){int n;cin >> n;vector<int> arr(n);vector<int> p(n);int pre = 0;for(int i = 0;i < n;i++){cin >> arr[i];pre += arr[i];p[i] = pre;}int res;int a,b;while(cin >> a >> b){if(a == 0) cout << p[b] << endl;else{res = p[b] - p[a - 1];cout << res << endl;}}
}
思考
acm输入输出模式中，当输出数量不确定时，可以使用while(cin >> a)这样的方式，当下一个输出为结尾或者回车就跳出循环了。
这种前缀和在计算一段区间的和时很有用，可以替代暴力计算。且可以用在二维数组中：[https://programmercarl.com/kamacoder/0044.开发商购买土地.html#思路]
算法刷题第二天，坚持！成为coding master