1. 学习滑动窗口

2.学习标准输入输出模式

3.学习文档代码随想录 (programmercarl.com) 数组总结

Leetcode 209.长度最小的子数组

 题目描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 

子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

解题思路：

1） 暴力解法：两个for循环，来不断的寻找符合条件的子序列，时间复杂度O（n^2），暴力解法是使用了两个for循环，一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成不断搜索区间的过程。

完整代码：目前会超时，直接贴的代码随想录中的代码

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++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = result < subLength ? result : subLength;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

2） 滑动窗口（代码随想录 (programmercarl.com)）：所谓滑动窗口就是不断的调节子序列的起始位置和终止位置，从而得出结果，那么滑动窗口是如何用一个for循环来完成这个操作呢？

首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么——是满足题目要求的总和大于等于target的长度最小的连续子数组；
• 如何移动窗口的起始位置——如果当前总和大于等于target，起始位置前移（缩小总和）；
• 如何移动窗口的结束位置——这里是for循环中的索引，要遍历数组；

分析：这题需要使用滑动窗口，开始思路想到了，但是忘记了这三点注意内容，重新复习总结！
 

 完整代码：滑动窗口

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        // 当result为最大值时，才能保证不断更新
        int result = INT32_MAX;
        int sum = 0;       // 滑动窗口数值之和
        int i = 0;         // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 满足条件，取子序列的长度
            // 每一次都更新最小的result
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; 
            // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

 Leetcode 59.螺旋矩阵II

本题没有思路！需要多加复习，考察对代码的掌控能力！

解题思路（代码随想录 (programmercarl.com)）： 

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

要如何画出这个螺旋排列的正方形矩阵呢？

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

 

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。

在画每一条边的时候，一会左开右闭，一会左闭右闭，一会又来左闭右开，岂能不乱。

代码如下，已经详细注释了每一步的目的，可以看出while循环里判断的情况是很多的，代码里处理的原则也是统一的左闭右开(左闭又开 最后一个值不填充)。
 

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组 最后结果返回的是一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置（x与y）
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值 初始值为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;
    }
};

58. 区间和（58. 区间和（第九期模拟笔试） (kamacoder.com)）

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

 使用常规解法，直接去判断这个区间，将这个区间中的数都累加一遍。会超时

 如果查询m次，每次查询的范围都是从0 到 n - 1，那么该算法的时间复杂度是 O(n * m) m 是查询   的次数，如果查询次数非常大的话，这个时间复杂度也是非常大的。

#include <iostream> // 包含标准输入输出流定义
#include <vector>

using namespace std;
int main() {
    int n, a, b;
    // 从标准输入读取一个整数n，表示接下来要输入的整数数量
    cin>>n;
    vector<int>vec(n);
    for(int i = 0; i<n; i++) {
        // 从标准输入读取一个整数并存储在向量vec的第i个位置
        cin>>vec[i];
    }
    // 开始一个while循环，只要能够从标准输入读取两个整数a和b，循环就继续
    while(cin >> a >> b) {
        int sum = 0;
        for(int i=a; i<=b; i++) {
            sum+=vec[i];
        }
        cout<<sum<<endl;
    }
}

解题思路 ：前缀和（重复利用之前计算过的子数组之和，降低区间查询需要的累加计算次数）58. 区间和 | 代码随想录 (programmercarl.com)

 假设一个数组，定义一个前缀和数组（每个元素是数组该位置之前所有元素之和），那么去计算[2-5]区间的区间和，就不需要重新遍历，只需要用p[5]-p[1]即可；所以后面每次求区间和的之后 我们只需要 O(1) 的操作；

特别注意： 在使用前缀和求解的时候，要特别注意 求解区间。                                                   

如下图，如果我们要求 区间下标 [2, 5] 的区间和，那么应该是 p[5] - p[1]，而不是 p[5] - p[2]。

 完整代码：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    // 声明三个整型变量n、a和b。n用于存储输入的数字个数，a和b用于后续的区间查询。
    int n, a, b;
    // 从标准输入读取一个整数n，表示接下来要输入的数字个数
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    // 循环n次，每次循环读取一个整数并更新前缀和
    for (int i = 0; i < n; i++) {
        // 从标准输入读取一个整数并存储在vec的第i个位置
        scanf("%d", &vec[i]);
        presum += vec[i];
        p[i] = presum;
    }
    // 使用一个循环来不断读取区间查询
    while (~scanf("%d%d", &a, &b)) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        printf("%d\n", sum);
    }
}

NOTE：特别注意输入输出的判断，对于输入输出不熟悉！