977.有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
卡哥的题目建议：建议大家先独立做题，然后看视频讲解，然后看文章讲解，然后在重新做一遍题，把题目AC，最后整理成今日当天的博客，拓展题目可以先不做。本题关键在于理解双指针思想。
做题思路：
有两种方法，暴力解法和双指针法。非递减顺序就是递增顺序，从小到大排。
暴力解法思路：就是将数组中的每个数平方后，再按从小到大的顺序排序。C++的sort函数是基于快速排序实现的，函数原型 void sort(first,last)，first是要排序的数组的起始地址，last是结束的地址（最后一个数据的后一个数据的地址）。如果利用迭代器，就可以用sort(a.begin(),a.end())，
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 const int N = 10;
5 int a[N]; //声明全局数组
6 int main()
7 {
8 int n; //数组的元素个数为 n
9 cout << "请输入数组的元素个数：" << endl;
10 cin >> n;
11 cout << "请输入数组：" << endl;
12 for (int i = 0; i < n; i++)
13 {
14 cin >> a[i]; //循环输入数组中的元素
15 }
16 for (int i = 0; i < n; i++)
17 {
18 a[i] *= a[i];
19 }
20 sort(a,a+n); //注意：这里没有利用迭代器
21 for (int i = 0; i < n; i++)
22 {
23 cout << a[i] << " "; //循环输入数组中的元素
24 }
25
26 return 0;
27 }
运行结果：
双指针法思路：
先看给的数组，nums = [-4,-1,0,3,10]，有负数；再平方后，nums = [16,1,0,9,100]，观察到平方后的数组两边的数比中间的大，所以我们可以考虑从第一个位置向后开始，最后一个位置向前开始，比较谁大，如果最后一个位置的数大的话，那就把这个数存放到新数组中，随着第一个位置和最后一个位置的移动，就能实现排序，有移动的动图，在文章链接里。这个两个位置就可以用双指针解决，其实就是两个变量。
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int main()
6 {
7 int n; //数组的元素个数为 n
8 cout << "请输入数组的元素个数：" << endl;
9 cin >> n;
10 cout << "请输入数组：" << endl;
11 for (int i = 0; i < n; i++)
12 {
13 cin >> a[i]; //循环输入数组中的元素
14 }
15 for (int i = 0; i < n; i++)
16 {
17 a[i] *= a[i];
18 }
19 int result[N];//放排好序的新数组
20 int k = n - 1; //新数组的下标为k,因为我们是先把大的数放进新数组，所以k值从n - 1开始
21 int first = 0;
22 int last = n - 1;
23 while (first <= last) //第一个位置的下标肯定比最后一个位置下标小或等于，才合法
24 {
25 if (a[first] < a[last])
26 {
27 result[k] = a[last];//最后一个位置比第一个位置大，就把最后一个位置的数放到新数组
28 k--; //比较完后，新数组的实际大小减一，更新下标
29 last--;//最后一个位置的数放到新数组，最后一个位置向前移动
30 }
31 else
32 {
33 result[k] = a[first];//第一个位置比最后一个位置大，
34 k--;//比较完后，新数组的实际大小减一，更新下标
35 first++;//第一个位置的数放到新数组，第一个位置向后移动
36 }
37 }
38 for (int i = 0; i < n; i++)
39 {
40 cout << result[i] << " "; //循环输入数组中的元素
41 }
42
43 return 0;
44 }
运行结果：
209.长度最小的子数组
卡哥的题目建议：本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。
做题思路：
有两种方法，暴力解法和双指针法。
暴力解法思路：这个题是为了找到和大于某个值的长度最小的连续子数组，所以先找到和大于某个值的子数组集合，再找长度最小的。可以用两层for循环，外层循环先定好从哪个地方开始找子数组，内层循环求和，从下标为0的地方开始找和大于某个值的位置，如果和大于某个值，就先记录下这个位置到外层循环定好的位置之间的长度，后面的位置没有必要寻找了。然后开始下一轮外层循环，同理.......再记录，更新长度；直到外层循环完后，才能把最短长度求出来。所以暴力解法会超时。
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int minSubArrayLen(int a[], int s)
6 {
7 int n = sizeof(a);
8 int result = INT32_MAX; // 最终的结果,INT32_MAX是int的最大值，2的16次方 - 1
9 int sum = 0; // 子数组的数值之和
10 int subLength = 0; // 子数组的长度
11 for (int i = 0; i < n; i++) //外层循环
12 {
13 sum = 0; //每一轮外层循环的时候，重置sum值，为了记录不同i值下的长度
14 for (int j = i; j < n; j++) //内层循环
15 {
16 sum += a[j];
17 if (sum >= s)//求和，从下标为0的地方开始找和大于某个值的位置
18 {
19 subLength = j - i + 1; //记录下这个位置到外层循环定好的位置之间的长度
20 result = result < subLength ? result : subLength;//如果小于最终长度，那最终长度不变；如果大于最终长度，那更新最终长度
21 break;
22 }
23 }
24 }
25 return result == INT32_MAX ? 0 : result;//如果result没有被赋值的话，就返回0，说明没有符合条件的子数组
26 }
27 int main()
28 {
29 int n; //数组的元素个数为 n
30 cout << "请输入数组的元素个数：" << endl;
31 cin >> n;
32 cout << "请输入数组：" << endl;
33 for (int i = 0; i < n; i++)
34 {
35 cin >> a[i]; //循环输入数组中的元素
36 }
37 int s;
38 cout << "请输入正整数 s :" << endl;
39 cin >> s;
40 cout << minSubArrayLen(a, s) << endl;
41 return 0;
42 }
运行结果：
双指针法思路：我们为了找到和大于某个值的长度最小的连续子数组，想像在数组上移动着找，刚开始会像暴力解法那样，定好一个起始位置，再移动另一个位置，但是如果两个位置都移动，效率就会提升很多，所以就引出了滑动窗口这个方法。在滑动窗口中，分起始位置和终止位置，终止位置用来找到和大于某个值的连续子数组集合；起始位置用来找最短长度，和暴力解法不同的是，当找到了和大于某个值的连续子数组集合后，就是终止位置暂时不移动了，同时记录下长度，起始位置此时从下标0开始移动，每移动一个位置，就用刚求好的和减去上一个位置的数，为了看还能不能找到更短的长度；如果不能的话，那只能移动终止位置，去重新找和大于某个值的连续子数组集合。同理，直到终止位置移动到数组尾部，且找不到最短长度了，就停止。
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int minSubArrayLen(int a[], int s)
6 {
7 int n = sizeof(a);
8 int result = INT32_MAX; // 最终的结果,INT32_MAX是int的最大值，2的16次方 - 1
9 int sum = 0; //滑动窗口的数值之和
10 int subLength = 0; //滑动窗口的长度
11 int i = 0; //滑动窗口起始位置
12 for (int j = 0; j < n; j++)
13 {
14 sum += a[j];
15 // 注意这里使用while，每次更新 i（起始位置），并不断比较子数组是否符合条件
16 while (sum >= s) {
17 subLength = (j - i + 1); // 取子数组的长度
18 result = result < subLength ? result : subLength;
19 sum -= a[i]; // 这里体现出滑动窗口的精髓之处，不断变更i（子数组的起始位置）
20 i++; //起始位置向后移动
21 }
22 }
23 return result == INT32_MAX ? 0 : result;//如果result没有被赋值的话，就返回0，说明没有符合条件的子数组
24 }
25 int main()
26 {
27 int n; //数组的元素个数为 n
28 cout << "请输入数组的元素个数：" << endl;
29 cin >> n;
30 cout << "请输入数组：" << endl;
31 for (int i = 0; i < n; i++)
32 {
33 cin >> a[i]; //循环输入数组中的元素
34 }
35 int s;
36 cout << "请输入正整数 s :" << endl;
37 cin >> s;
38 cout << minSubArrayLen(a, s) << endl;
39 return 0;
40 }
运行结果：
59.螺旋矩阵II
卡哥的题目建议：本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
做题思路：
我感觉这里看视频和文章就能理解，就是要想到矩阵可以是一个正方形，从总共能走的圈数，再从正方形4条边入手，这些边可以当做在一个区间上，写一些区间上的边界的限制条件。结合之前做的题，会想到左闭右闭，左闭右开........
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int main()
5 {
6 int n;
7 cout << "请输入一个正整数 n：" << endl;
8 cin >> n;
9 int res[N][N] = { 0 };
10 int startx = 0, starty = 0; // 定义每循环一个圈的起始位置,相当于一个坐标（startx, starty)
11 int loop = n / 2; // 这个可以画图理解，每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
12 int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
13 int count = 1; // 用来给矩阵中每一个空格赋值
14 int offset = 1; // 每一圈右边界向里收缩一位
15 int i, j;
16 while (loop--)
17 {
18 i = startx;
19 j = starty;
20
21 // 下面开始的四个for就是模拟转了一圈
22 // 模拟填充上行从左到右(左闭右开)
23 for (j = starty; j < n - offset; j++) //行不变，列变，所以列的初始值一开始为0，右开，右边界值不能取到
24 {
25 res[startx][j] = count++;
26 }
27 // 模拟填充右列从上到下(左闭右开)
28 for (i = startx; i < n - offset; i++) //列不变，行变，所以行的初始值一开始为0，右开，右边界值不能取到
29 {
30 res[i][j] = count++;
31 }
32 // 模拟填充下行从右到左(左闭右开)
33 for (; j > starty; j--) //走到了i, j 的最大值处，不需要设行列的初始值，行不变，列变，列不能比0小
34 {
35 res[i][j] = count++;
36 }
37 // 模拟填充左列从下到上(左闭右开)
38 for (; i > startx; i--)//走到了 i 的最大值处........
39 {
40 res[i][j] = count++;
41 }
42
43 // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
44 startx++;
45 starty++;
46
47 // offset 控制每一圈里每一条边遍历的长度
48 offset += 1;
49 }
50
51 // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
52 if (n % 2 == 1)
53 {
54 res[mid][mid] = count;
55 }
56 for (int i = 0; i < n; i++) //矩阵为 n*n
57 {
58 cout << "[";
59 for (int j = 0; j < n; j++)
60 {
61 cout << res[i][j] << " ";
62 }
63 cout << "]";
64 cout << endl;
65 }
66 return 0;
67 }
运行结果：
最后，数组的总结看一下卡哥的吧。