算法：数组part02: 209. 长度最小的子数组 +
算法：数组part02: 209. 长度最小的子数组 +
209. 长度最小的子数组
题目：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE（思想较难，看视频复习）
思想
- 找出长度最小的子数组，用暴力解法，两层for循环列出所有的可能情况（以i为头以j为尾，这样i从头遍历到尾，找到以数组所以元素为头的子数组）可以解题；
- 要想用一层for实现上面的效果，就需要用到滑动窗口（双指针）的思想，for循环滑动窗口的右边界，左边界在这层for的逻辑中去修改；就可以达到O(n)的时间复杂度；
解题
暴力解法
//C++版
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int result = INT32_MAX; // 最终的结果int sum = 0; // 子序列的数值之和int subLength = 0; // 子序列的长度for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为isum = 0;for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为jsum += nums[j];if (sum >= s) { // 一旦发现子序列和超过了s，更新resultsubLength = j - i + 1; // 取子序列的长度result = result < subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break}}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列return result == INT32_MAX ? 0 : result;}
};
正解
class Solution {public int minSubArrayLen(int target, int[] nums) {//利用滑动窗口（左右指针指示滑动窗口两端，本身还是双指针的思想）int left=0;int sum=0;//初始的result需要设为整数的最大值int result=Integer.MAX_VALUE;//记录满足条件的子串长度int sublength=0;for(int right=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){sublength=right-left+1;result=Math.min(sublength,result);sum-=nums[left++];}}return result==Integer.MAX_VALUE?0:result;}
}////这个是参考答案，要更好理解，上面的是我写的
class Solution {// 滑动窗口public int minSubArrayLen(int s, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= s) {result = Math.min(result, right - left + 1);sum -= nums[left++];}}return result == Integer.MAX_VALUE ? 0 : result;}
}
总结
for循环循环的是滑动窗口的右边界，左边界在这个循环逻辑的内部利用while()去改变;感觉这个思想要记下来，第一次接触基本想不出；
59.螺旋矩阵II
题目：https://leetcode.cn/problems/spiral-matrix-ii/description/
文章链接：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
思想
文章中总结的思路很好,要坚持循环不变量的原则：搞清区间的边界，以及每次循环的判断条件要一样；
边界确定：每行或每列的末尾不属于本行，而作为下一行的开始
螺旋矩阵的n：n为偶数loop=2/n，n为奇数就需要单独处理最内部的一个位置；
解题
class Solution {public int[][] generateMatrix(int n) {int nums[][]=new int[n][n];//循环圈数int loop=0;int startX=0;int startY=0;int i,j;//用来表示每行最后几个不包含int offset=1;//用来表示填充的数字int count=1;int mid=n/2;while(loop<n/2){//下面的四个for就是模拟转了一圈//首先是左上到右上for(j=startY;j<n-offset;j++){nums[startX][j]=count++;}//右上到右下for(i=startX;i<n-offset;i++){nums[i][j]=count++;}//右下到左下for(;j>startY;j--){nums[i][j]=count++;}//左下到左上for(;i>startX;i--){nums[i][j]=count++;}startX++;startY++;loop++;offset++;}//奇数的情况单独给中间元素赋值if(n%2!=0){nums[mid][mid]=count;}return nums;}
}////这个是参考答案，要更好理解，上面的是我写的
class Solution {public int[][] generateMatrix(int n) {int[][] nums = new int[n][n];int startX = 0, startY = 0; // 每一圈的起始点int offset = 1;int count = 1; // 矩阵中需要填写的数字int loop = 1; // 记录当前的圈数int i, j; // j 代表列, i 代表行;while (loop <= n / 2) {// 顶部// 左闭右开，所以判断循环结束时， j 不能等于 n - offsetfor (j = startY; j < n - offset; j++) {nums[startX][j] = count++;}// 右列// 左闭右开，所以判断循环结束时， i 不能等于 n - offsetfor (i = startX; i < n - offset; i++) {nums[i][j] = count++;}// 底部// 左闭右开，所以判断循环结束时， j != startYfor (; j > startY; j--) {nums[i][j] = count++;}// 左列// 左闭右开，所以判断循环结束时， i != startXfor (; i > startX; i--) {nums[i][j] = count++;}startX++;startY++;offset++;loop++;}if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值nums[startX][startY] = count;}return nums;}
}总结
- 螺旋矩阵II的关键点在于循环不变量：确定边界，循环条件不变；
- 时间复杂度为O(n2);