一、長度最小的子數組（滑動窗口）
leetcode 209 長度最小子數組
這道題的核心思想就是使用滑動窗口，滑動窗口三板斧：
- 初始位置i
- 滑動窗口長度j-i+1
- 結束位置j
我們在寫代碼時是通過for循環來控制結束位置j，而初始位置i是在滿足條件的情況下才向前移動的
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int i=0,j=0;//i是窗口起始位置，j是終止位置int result = INT32_MAX; //因為要找到最小的，如果初始成0，那0永遠是最小的int subLength = 0; //子數組長度int sum = 0;for(j=0;j<nums.size();j++){sum += nums[j]; //一直疊加到終止位置while(sum >= target){ //滿足條件后要判斷此時字串長度是否更小，同時移動起始位置isubLength = j-i+1;if(subLength < result) result = subLength;sum -= nums[i];//i指針移動，sum減去一個值i++;}}return result==INT32_MAX ? 0:result;}
};二、模擬 - 螺旋矩陣Ⅱ
leetcode 59 螺旋矩陣
這道題目就是要模擬按照順時針畫矩陣的過程
- 填充上行從左到右
- 填充右列從上到右
- 填充下列從右到左
- 填充左列從下到上
同時需要注意的是每一行（列）的處理范圍要保持一致——左閉右開
我們首先要確定總共要繞多少圈（loop）,接著就在每一圈內順時針填充行列，一定要注意邊界處理條件
class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> result(n,vector<int>(n,0));int loop = n/2; //所要走的圈數int startx = 0,starty = 0; //每一圈開始的起始位置int mid = n/2; //中間值（在n為奇數時需要特殊處理）int offset = 1; //用于處理每一圈的邊界int i,j;int count = 1;//向矩陣中填的數while(loop){i = startx;j = starty;//四個for循環模擬for(j;j<n-offset;j++){ //模擬上行從左到右result[i][j] = count;count++;}for(i;i<n-offset;i++){//模擬右列從上到下result[i][j] = count++;}for(j;j>starty;j--){//模擬下行從右到左（注意邊界條件，同時這里循環變量剛好從上面結束的j開始）result[i][j] = count++;}for(i;i>startx;i--){//模擬左列從下到上result[i][j] = count++;}startx++;starty++;offset++; //表示邊界的結束位置要少一位（因為下一處繞的圈變小了）loop--;}//處理n是邊界的情況if(n%2 != 0){result[mid][mid] = count;}return result;}
};三、一維前綴和
題目
前綴和用來求解區間之和，一維指的是求解的是一維數組的前綴和。
前綴和的核心思想就是設置了一個前綴和數組sum
sum數組初始化如下：
- sum[0] = Array[0]
- i>0,sum[i] = sum[i-1] + Array[i]
接下來就可以利用sum數組來求解數組區間[a,b]的和，利用下面的公式計算：
- 當a = 0 時 ， result = sum[b]
- 當a>0時，result = sum[b] - sum[a-1]
#include<bits/stdc++.h>
using namespace std;int main(){int n,i;int a,b;int result;cin>>n;vector<int>Array(n);vector<int>sum(n,0);for(i=0;i<n;i++){cin>>Array[i];}sum[0] = Array[0];for(i=1;i<n;i++){sum[i] = sum[i-1] + Array[i];}while(cin>>a>>b){if(a==0) result = sum[b];else result = sum[b] - sum[a-1]; printf("%d\n",result);}
}
