算法第二天|209.长度最小的子数组，59.螺旋矩阵2， 区间和，开发商购买土地

209.长度最小的子数组class Solution { public: int minSubArrayLen(int target, vectorint nums) { int num nums.size(); int l 0, ans num 1, sum 0; for(int r 0; r num; r){ sum nums[r]; while(sum target){ ans min(ans, r-l1); sum - nums[l]; l; } } return ans num ? ans:0; } };思路滑窗右指针循环迭代数组内依次相加检测到有超过target的比较最小的减去左指针58. 区间和#include iostream #include vector using namespace std; int main() { int n, a, b; cin n; vectorint arr(n); vectorint ans(n); int temp 0; for (int i 0; i n; i) { cin arr[i]; temp arr[i]; ans[i] temp; } while (cin a b) { int sum; if (a 0) sum ans[b]; else sum ans[b] - ans[a - 1]; cout sum endl; } }思路第一次接触到前缀和概念在构造数组的时候计算出区间和59螺旋矩阵2class Solution { int DIRS[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; public: vectorvectorint generateMatrix(int n) { vector ans(n, vectorint(n)); int i 0, j 0, di 0; for (int val 1; val n * n; val) { ans[i][j] val; int x i DIRS[di][0]; int y j DIRS[di][1]; if (x 0 || x n || y 0 || y n || ans[x][y]) { di (di 1) % 4; } i DIRS[di][0]; j DIRS[di][1]; } return ans; } };DIRS代表四个方向开发商购买土地#include iostream #include vector #include climits using namespace std; int main () { int n, m; cin n m; int sum 0; vectorvectorint vec(n, vectorint(m, 0)) ; for (int i 0; i n; i) { for (int j 0; j m; j) { cin vec[i][j]; sum vec[i][j]; } } // 统计横向 vectorint horizontal(n, 0); for (int i 0; i n; i) { for (int j 0 ; j m; j) { horizontal[i] vec[i][j]; } } // 统计纵向 vectorint vertical(m , 0); for (int j 0; j m; j) { for (int i 0 ; i n; i) { vertical[j] vec[i][j]; } } int result INT_MAX; int horizontalCut 0; for (int i 0 ; i n; i) { horizontalCut horizontal[i]; result min(result, abs(sum - horizontalCut - horizontalCut)); } int verticalCut 0; for (int j 0; j m; j) { verticalCut vertical[j]; result min(result, abs(sum - verticalCut - verticalCut)); } cout result endl; }