10.長度最小的子數組
（力扣209題）
給定一個含有 n 個正整數的數組和一個正整數 target 。
找出該數組中滿足其總和大于等于 target 的長度最小的 子數組 [numsl, numsl+1, ..., 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
使用 滑動窗口
10.1 滑動窗口
滑動窗口，就是不斷的調節子序列的起始位置和終止位置，從而得出我們要想的結果
滑動窗口也可以理解為雙指針法的一種，
使用一個for循環，j是滑動窗口的終止位置，i是起始位置，也是動態指針，
窗口的起始位置i：當前窗口值大于等于傳入的值，i移動；
窗口的結束位置j：j就是遍歷數組的指針，是for循環里的索引
代碼
#include <iostream>
#include <vector>
using namespace std;
// 暴力破解
class Solution1
{
public:int minSubArrayLen(int target, vector<int> &nums){int result = INT32_MAX; // 最終的結果 INT32_MAX 是一個常量，表示 32 位有符號整數的最大值。int sum = 0; // 子序列的數值之和int length = 0; // 子序列的長度for (int i = 0; i < nums.size(); i++) // 字序列起點{sum = 0;for (int j = i; j < nums.size(); j++) // 字序列終點{// 遍歷的數組元素存入子序列sum += nums[j];if (sum >= target){// 總和大于等于目標值length = j - i + 1; // 子序列的長度// 找符合條件最小的長度result = length < result ? length : result;break;}}}// result結果沒有變化，沒有找到return result == INT32_MAX ? 0 : result;}
};class Solution
{
public:int minSubArrayLen(int target, vector<int> &nums){int result = INT32_MAX; // 最終的結果 INT32_MAX 是一個常量，表示 32 位有符號整數的最大值。int sum = 0; // 子序列的數值之和int length = 0; // 子序列的長度int i = 0; // 窗口的起始位置for (int j = 0; j < nums.size(); j++) // 遍歷數組{// 遍歷的數組元素存入子序列sum += nums[j];while (sum >= target){// 子序列大于目標值開始位置變化 尋找最小的序列length = j - i + 1;result = result < length ? result : length;sum -= nums[i++];}}// 沒找到 返回0return result == INT32_MAX ? 0 : result;}
};
int main()
{vector<int> arr1 = {2, 3, 1, 2, 4, 3};vector<int> arr2 = {1, 4, 4};vector<int> arr3 = {1, 1, 1, 1, 1, 1, 1, 1};Solution s;cout << s.minSubArrayLen(7, arr1) << endl;cout << s.minSubArrayLen(4, arr2) << endl;cout << s.minSubArrayLen(11, arr3) << endl;return 0;
}11.水果成籃
（力扣904題）
你正在探訪一家農場，農場從左到右種植了一排果樹。這些樹用一個整數數組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。
你想要盡可能多地收集水果。然而，農場的主人設定了一些嚴格的規矩，你必須按照要求采摘水果：
- 你只有 兩個 籃子，并且每個籃子只能裝 單一類型 的水果。每個籃子能夠裝的水果總量沒有限制。
- 你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個水果 。采摘的水果應當符合籃子中的水果類型。每采摘一次，你將會向右移動到下一棵樹，并繼續采摘。
- 一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。
給你一個整數數組 fruits ，返回你可以收集的水果的 最大 數目。
示例 1：
輸入：fruits = [1,2,1]
輸出：3
解釋：可以采摘全部 3 棵樹。
示例 2：
輸入：fruits = [0,1,2,2]
輸出：3
解釋：可以采摘 [1,2,2] 這三棵樹。
如果從第一棵樹開始采摘，則只能采摘 [0,1] 這兩棵樹。
示例 3：
輸入：fruits = [1,2,3,2,2]
輸出：4
解釋：可以采摘 [2,3,2,2] 這四棵樹。
如果從第一棵樹開始采摘，則只能采摘 [1,2] 這兩棵樹。
示例 4：
輸入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：可以采摘 [1,2,1,1,2] 這五棵樹。
和上面的題的區別是這個是找最長子序列
- 思路
- 初始化滑動窗口的左右邊界
i和j，以及一個哈希表basket來記錄窗口內水果的種類和數量。 - 遍歷數組，將水果加入窗口（
basket），并更新其數量。 - 當窗口內的水果種類超過兩種時，收縮窗口的左邊界（
i），減少對應水果的數量，直到窗口內水果種類不超過兩種。 - 在每次循環中，更新最長子數組的長度（
result），即當前窗口的大小（j - i + 1）。 - 最終返回
result，即最長的滿足條件的子數組長度
實例
#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;
// 這個是找最長的序列
class Solution
{
public:int totalFruit(vector<int> &fruits){// 收集最終水果的數目int result = 0;// /籃子中的水果種類數量unordered_map<int, int> basket;// 滑動窗口的開始位置int i = 0;for (int j = 0; j < fruits.size(); j++){basket[fruits[j]]++;// 籃子水果種類大于2while(basket.size() > 2){basket[fruits[i]]--;// 如果某種水果數量為0，從籃子中移除if( basket[fruits[i]] == 0){basket.erase(fruits[i]);}i++;}result = max(result, j - i + 1);}return result;}};
給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
12 螺旋矩陣
（力扣59題）
示例 1：
輸入：n = 3
輸出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
輸入：n = 1
輸出：[[1]]
核心思路是通過逐層填充矩陣的外圈，逐步向內收縮，直到填充完整個矩陣
- 初始化一個 n×n 的二維數組
res，所有元素初始值為 0。 - 使用變量
startx和starty表示當前層的起始位置，loop表示需要填充的圈數，offset表示當前層的邊界偏移量。 - 使用一個循環逐層填充矩陣，每次循環填充當前層的上、右、下、左四條邊。
- 在填充每條邊時，通過
for循環依次賦值，并更新count。 - 每完成一層后，更新
startx、starty和offset，進入內層繼續填充。 - 如果矩陣的維度 n 是奇數，最后單獨填充矩陣中心的值。
實例
// 給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，
// 且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。
#include <iostream>
#include <vector>
using namespace std;class Solution
{
public:vector<vector<int>> generateMatrix(int n){// 大小為 n×n 的二維向量，其所有元素的初始值都為 0。vector<vector<int>> res(n, vector<int>(n, 0));int startx = 0, starty = 0; // 數組的行列起始位置int loop = n / 2; // 循環次數int mid = n / 2; // 中間的值 n = 5 中間的位置就是2，2int count = 1; // 給數組賦值int offset = 1; // 縮進 控制的終止位置int i, j = 0;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 進入內圈startx++;starty++;// 進入內圈偏移量+1以便同步offset++;}// / 如果n為奇數的話，需要單獨給矩陣最中間的位置賦值 就是countif (n % 2) {res[mid][mid] = count;}return res;}
};
int main()
{int n = 0;cout << "請輸入一個正整數：";cin >> n;Solution s1;vector<vector<int>> res = s1.generateMatrix(n);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cout << res[i][j] << " ";}cout << endl;}return 0;
}
