代码随想录—day2—滑动窗口与前缀和

滑动窗口题例:209. 长度最小的子数组 - 力扣LeetCode给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回0。示例 1输入target 7, nums [2,3,1,2,4,3]输出2解释子数组[4,3]是该条件下的长度最小的子数组。示例 2输入target 4, nums [1,4,4]输出1示例 3输入target 11, nums [1,1,1,1,1,1,1,1]输出01.暴力算法(O(n²))(超时了......)class Solution { public: int minSubArrayLen(int target, vectorint nums) { int nnums.size(); vectorintans; ans.push_back(INT_MAX); bool xfalse; for(int i0;in;i) { int sum0; int cnt0; for(int ji;jn;j) { sumnums[j]; cnt; if(sumtargetcntans.back()) { ans[0]cnt; xtrue; break; } } } if(!x){ return 0; }else{ return ans[0]; } } };1.先在ans这个记录更小长度的数组中插入INT_MAX确保后续ans的更新。2.写两个for循环第一个for循环用于遍历数组第二个for循环用于数组元素的累加以及段落数组长度的记录。3.当sumtarget且cntans.back()(即这个段落数组的长度更小时),更新ans,同时在这个i值下符合条件的段落数组寻找完毕,跳出这一层循环,继续寻找新的起点。(这里原本是没有写break的但那样白白浪费了符合条件后到jn这么多的时间)4.考虑到整个数组的和都达不到ans的情况,肯定不能返回INT_MAX,要返回0对于这种情况发现单单从数组长度或者其中具体元素特征很难判断但是可以从ans是否更新过来判断那就引入bool x记录是否发生过更新没有发生过更新就返回0.2.滑动窗口(O(n))class Solution { public: int minSubArrayLen(int target, vectorint nums) { int nnums.size(); int i0; int resultINT_MAX; bool xfalse; int sum0; for(int j0;jn;j) { sumnums[j]; while(sumtarget) { resultmin(result,j-i1); sumsum-nums[i]; xtrue; } } if(!x){ return 0; }else{ return result; } } };1.定义快指针j和慢指针i快指针j先用来获得一个“大窗口”的和慢指针i用来维护窗口(减去nums[i])2.当sumtarget时,先将窗口长度记录在result中然后开始维护窗口减去最左侧的元素不断调整窗口直到sumtarget这一个j下,窗口达到最小。同时通过x记录下sumtarget这一事件方便后续判断return 0还是return result3.第一个for循环循环次数最多为n次同时i最多循环n次故时间复杂度为O(n)O(n)O(n)模拟题例:59. 螺旋矩阵 II - 力扣LeetCode(感觉好难被初见杀了......)给你一个正整数n生成一个包含1到n2所有元素且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。示例 1输入n 3输出[[1,2,3],[8,9,4],[7,6,5]]示例 2输入n 1输出[[1]]class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorintans(n,vectorint(n,0)); int cnt1; int left0,rightn-1,up0,downn-1; while(cntn*n) { for(int jleft;jright;j) { ans[up][j]cnt; } up; for(int iup;idown;i) { ans[i][right]cnt; } right--; for(int jright;jleft;--j) { ans[down][j]cnt; } down--; for(int idown;iup;--i) { ans[i][left]cnt; } left; } return ans; } };只需定义左右上下边界在填充数字的过程中调整边界即可。前缀和题例:58. 区间和 | 前缀和 | 区间查询 | 代码随想录题目描述给定一个整数数组 Array请计算该数组在每个指定区间内元素的总和。输入描述第一行输入为整数数组 Array 的长度 n接下来 n 行每行一个整数表示数组的元素。随后的输入为需要计算总和的区间直至文件结束。输出描述输出每个指定区间内元素的总和。输入示例5 1 2 3 4 5 0 1 1 3输出示例3 9数据范围0 n 1000001.暴力算法(O(nm*l)(m为查询次数,l为平均长度))#include iostream #include vector using namespace std; int main() { int n, a, b; cin n; vectorint vec(n); for (int i 0; i n; i) cin vec[i]; while (cin a b) { int sum 0; // 累加区间 a 到 b 的和 for (int i a; i b; i) sum vec[i]; cout sum endl; } }非常暴力直接下标从a到b累加。最坏情况下a和b差了n-1这时候就有超时的风险2.前缀和(O(nl))#includeiostream #includevector #includealgorithm using namespace std; int main() { int n; cin n; int sum1 0; vectorintarray(n); vectorintsum(n); for (int i 0; i n; i) { int x; cin x; array[i] x; sum1 x; sum[i] sum1; } int a,b; while (cin a b) { if (a 0) { cout sum[b] ; } else { cout sum[b] - sum[a - 1]; } } return 0; }简单来说就是写一个for循环累加数组的和把从0开始到每个下标的元素和存储在一个数组里这么写与暴力写法的不同点在于在第一个for循环中额外写了一些代码用来建立新数组将暴力写法中时间复杂度可能为O(n)的累加换成了现在O(1)的数组元素相减题例:44. 开发商购买土地 | 前缀和 | 矩阵划分 | 代码随想录【题目描述】在一个城市区域内被划分成了n * m个连续的区块每个区块都拥有不同的权值代表着其土地价值。目前有两家开发公司A 公司和 B 公司希望购买这个城市区域的土地。现在需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而由于城市规划的限制只允许将区域按横向或纵向划分成两个子区域而且每个子区域都必须包含一个或多个区块。为了确保公平竞争你需要找到一种分配方式使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。注意区块不可再分。【输入描述】第一行输入两个正整数代表 n 和 m。接下来的 n 行每行输出 m 个正整数。输出描述请输出一个整数代表两个子区域内土地总价值之间的最小差距。【输入示例】3 3 1 2 3 2 1 3 1 2 3【输出示例】0【提示信息】如果将区域按照如下方式划分1 2 | 3 2 1 | 3 1 2 | 3两个子区域内土地总价值之间的最小差距可以达到 0。【数据范围】1 n, m 100n 和 m 不同时为 1。#includeiostream #includevector #includealgorithm using namespace std; int main() { int m, n;//m行n列 while (cin m nm0n0) { vectorvectorintaaa(m, vectorint(n)); vectorinthorizontal(m,0); vectorintvertical(n,0); int sum 0; if (m 0 || n 0) { break; } for (int i 0; i m; i) { for (int j 0; j n; j) { cin aaa[i][j]; sum aaa[i][j]; } } for (int i 0; i m; i) { for (int j 0; j n; j) { horizontal[i]aaa[i][j]; } } for (int j 0; j n; j) { for (int i 0; i m; i) { vertical[j] aaa[i][j]; } } int horizontalcut 0; int verticalcut 0; int result1 INT_MAX; for (int i 0; i m-1; i) { horizontalcut horizontal[i]; result1 min(result1, abs(sum - horizontalcut * 2)); } for (int j 0; j n-1; j) { verticalcut vertical[j]; result1 min(result1, abs(sum - verticalcut * 2)); } cout result1; } return 0; }简单来说就是在两个数组里存储每行的和和每列的和然后for循环进行切割线的遍历定义result1存储切割线两边之差的较小值。