5、滑动窗口 ---209给定一个含有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] 输出0接下来就开始介绍数组操作中另一个重要的方法滑动窗口。所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们想要的结果。在暴力解法中是一个for循环滑动窗口的起始位置一个for循环为滑动窗口的终止位置用两个for循环 完成了一个不断搜索区间的过程。那么滑动窗口如何用一个for循环来完成这个操作呢。首先要思考 如果用一个for循环那么应该表示 滑动窗口的起始位置还是终止位置。如果只用一个for循环来表示 滑动窗口的起始位置那么如何遍历剩下的终止位置此时难免再次陷入 暴力解法的怪圈。所以 只用一个for循环那么这个循环的索引一定是表示 滑动窗口的终止位置。可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。class Solution { public: int minSubArrayLen(int target, vectorint nums) { int result 999999999; int length 0; int i 0; int sum 0; for (int j 0;j nums.size(); j){ sum nums[j] sum; while (sum target){ length j - i 1; if (length result){ result length; } sum sum - nums[i]; i; } } if (result 999999999){result 0;} return result; } };一些录友会疑惑为什么时间复杂度是O(n)。不要以为for里放一个while就以为是O(n^2)啊 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n)。6、螺旋矩阵给你一个正整数n生成一个包含1到n2所有元素且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。示例 1输入n 3 输出[[1,2,3],[8,9,4],[7,6,5]]思路这道题目可以说在面试中出现频率较高的题目本题并不涉及到什么算法就是模拟过程但却十分考察对代码的掌控能力。要如何画出这个螺旋排列的正方形矩阵呢相信很多同学刚开始做这种题目的时候上来就是一波判断猛如虎。结果运行的时候各种问题然后开始各种修修补补最后发现改了这里那里有问题改了那里这里又跑不起来了。大家还记得我们在这篇文章数组每次遇到二分法都是一看就会一写就废 (opens new window)中讲解了二分法提到如果要写出正确的二分法一定要坚持循环不变量原则。而求解本题依然是要坚持循环不变量原则。模拟顺时针画矩阵的过程:填充上行从左到右填充右列从上到下填充下行从右到左填充左列从下到上由外向内一圈一圈这么画下去。可以发现这里的边界条件非常多在一个循环中如此多的边界条件如果不按照固定规则来遍历那就是一进循环深似海从此offer是路人。这里一圈下来我们要画每四条边这四条边怎么画每画一条边都要坚持一致的左闭右开或者左开右闭的原则这样这一圈才能按照统一的规则画下来。那么我按照左闭右开的原则来画一圈大家看一下这里每一种颜色代表一条边我们遍历的长度可以看出每一个拐角处的处理规则拐角处让给新的一条边来继续画。这也是坚持了每条边左闭右开的原则。一些同学做这道题目之所以一直写不好代码越写越乱。就是因为在画每一条边的时候一会左开右闭一会左闭右闭一会又来左闭右开岂能不乱。代码如下已经详细注释了每一步的目的可以看出while循环里判断的情况是很多的代码里处理的原则也是统一的左闭右开。整体C代码如下​ class Solution { public: vectorvectorint generateMatrix(int n) { vectorvectorint res(n, vectorint(n, 0)); // 使用vector定义一个二维数组 int startx 0, starty 0; // 定义每循环一个圈的起始位置 int loop n / 2; // 每个圈循环几次例如n为奇数3那么loop 1 只是循环一圈矩阵中间的值需要单独处理 int mid n / 2; // 矩阵中间的位置例如n为3 中间的位置就是(11)n为5中间位置为(2, 2) int count 1; // 用来给矩阵中每一个空格赋值 int offset 1; // 需要控制每一条边遍历的长度每次循环右边界收缩一位 int i,j; while (loop --) { i startx; j starty; ​ // 下面开始的四个for就是模拟转了一圈 // 模拟填充上行从左到右(左闭右开) for (j; j n - offset; j) { res[i][j] count; } // 模拟填充右列从上到下(左闭右开) for (i; i n - offset; i) { res[i][j] count; } // 模拟填充下行从右到左(左闭右开) for (; j starty; j--) { res[i][j] count; } // 模拟填充左列从下到上(左闭右开) for (; i startx; i--) { res[i][j] count; } ​ // 第二圈开始的时候起始位置要各自加1 例如第一圈起始位置是(0, 0)第二圈起始位置是(1, 1) startx; starty; ​ // offset 控制每一圈里每一条边遍历的长度 offset 1; } ​ // 如果n为奇数的话需要单独给矩阵最中间的位置赋值 if (n % 2) { res[mid][mid] count; } return res; } };