1.二分查找

2.快慢 雙指針

代碼隨想錄day1-CSDN博客

3.滑動窗口

滑動窗口就是有一個起始位置，一個終止位置，通過調節起始位置和終止位置得到我們想要的結果。

外面一層for循環??? 用來更新終止位置?? 不滿足條件 終止位置右移

里面一層while循環? 用來更新起始位置?? 滿足條件 起始位置右移

209. 長度最小的子數組 - 力扣（LeetCode）

int minSubArrayLen(int target, vector<int>& nums) {int i = 0;int reslut = 100001;int subL = 0;int sum = 0;for(int j = 0; j < nums.size(); j++){sum += nums[j];while(sum >= target){subL = j - i + 1;reslut = min(reslut, subL);sum -= nums[i];i++;}}if(reslut == 100001)return 0;else return reslut;}

904. 水果成籃 - 力扣（LeetCode）

int totalFruit(vector<int>& fruits) {int i = 0;int result = 0;unordered_map<int, int> kind; //記錄水果種類數for(int j = 0; j < fruits.size(); j++){kind[fruits[j]]++;while(kind.size() > 2){kind[fruits[i]]--;if(kind[fruits[i]] == 0){kind.erase(fruits[i]); //如果某種水果數量等于0，從哈希表中移除}i++;}result = max(result, j - i + 1);}return result;}

76. 最小覆蓋子串 - 力扣（LeetCode）

string minWindow(string s, string t) {if(s.empty() || t.empty() || s.size() < t.size())return "";int result = INT_MAX;int i = 0;unordered_map<char, int>t_count;unordered_map<char, int> window_count;for(int j = 0; j < t.size(); j++){t_count[t[j]]++;}int num = 0;int left = 0;for(int j = 0; j < s.size(); j++){window_count[s[j]]++;if(window_count[s[j]] == t_count[s[j]]){num++;}while(num == t_count.size()){int temp = j - i + 1;if(temp < result){result = temp;left = i;}if(t_count.find(s[i]) != t_count.end()){if(window_count[s[i]] == t_count[s[i]]){num--;}//本來有可能大于或等于window_count[s[i]]--;}i++;}}return result == INT_MAX ? "":s.substr(left, result);}

4.螺旋矩陣模擬

左閉右開，循環模擬

59. 螺旋矩陣 II - 力扣（LeetCode）

vector<vector<int>> generateMatrix(int n) {int starx = 0, stary = 0;int offset = 1;vector<vector<int>> re(n, vector<int>(n,0));int count = 1;int i, j;while(offset <= n/2){i = starx;j = stary;for(; j < n - offset; j++){re[i][j] = count++;}for(; i < n - offset; i++){re[i][j] = count++;}for(; j > stary; j--){re[i][j] = count++;}for(; i > starx; i--){re[i][j] = count++;}offset++;starx++;stary++;}if(n % 2 != 0)re[n/2][n/2] = count;return re;}

?54. 螺旋矩陣 - 力扣（LeetCode）

vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size() == 0 || matrix[0].size() == 0)return {};vector<int> re; int starx = 0, stary = 0;int w = matrix[0].size();int h = matrix.size();int i, j;int offset = 1;while(offset <= min(w,h)/2){i = starx;j = stary;for(; j < w - offset; j++){re.push_back(matrix[i][j]);}for(;i < h - offset; i++){re.push_back(matrix[i][j]);}for(; j > stary; j--){re.push_back(matrix[i][j]);}for(; i > starx; i--){re.push_back(matrix[i][j]);}offset++;starx++;stary++;}if(h % 2 != 0 && w >= h){int offset = h/2;for(int j = offset; j < w - offset; j++){re.push_back(matrix[offset][j]);}}else if(w % 2 != 0 && w < h){int offset = w/2;for(int i = offset; i < h - offset; i++){re.push_back(matrix[i][offset]);}}return re;}

5.區間和

把前綴和保存起來后面直接用

58. 區間和（第九期模擬筆試）

#include<iostream>
#include<vector>
using namespace std;int main(){int n, a, b;cin >> n;int re = 0;vector<int> vec(n);vector<int> sum(n);   // 前綴和for(int i = 0; i < n; i++){int t;cin >> t;vec[i] = t;if(i == 0)sum[i] = t;else sum[i] = t + sum[i-1];}while(cin >> a >> b){if(a == 0)re = sum[b];else re = sum[b] - sum[a-1];cout << re << endl;}}

44. 開發商購買土地（第五期模擬筆試）

#include<iostream>
#include<vector>
#include <climits>
using namespace std;int main(){int n, m;cin >> n >> m;int sum = 0;vector<vector<int>> vec(n, vector<int>(m, 0));vector<int> w(n, 0);  //橫向vector<int> h(m, 0);  //縱向for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){int t = 0;cin >> vec[i][j];sum += vec[i][j];w[i] += vec[i][j];}}for(int j = 0; j < m; j++){for(int i = 0; i < n; i++){h[j] += vec[i][j];}}int result = INT_MAX;int t = 0;for(int i  = 0; i < n; i++){t += w[i];result = min(result, abs(sum - t - t));}t = 0;for(int j = 0; j < m; j++){t += h[j];result = min(result, abs(sum - t - t));}cout << result << endl;
}