二分探索#
第一種書寫法（左閉右閉）#
//第一種書寫法
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定義target在左閉右閉的區間裡，[left, right]
while (left <= right) { // 當left==right，區間[left, right]依然有效，所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同於(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左區間，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右區間，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 陣列中找到目標值，直接返回下標
}
}
// 未找到目標值
return -1;
}
};
第二種書寫法（左閉右開）#
// 版本二
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定義target在左閉右開的區間裡，即：[left, right)
while (left < right) { // 因為left == right的時候，在[left, right)是無效的空間，所以使用 <
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle; // target 在左區間，在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右區間，在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 陣列中找到目標值，直接返回下標
}
}
// 未找到目標值
return -1;
}
};
雙指針法#
移除元素#
雙指針法 (快慢指針法): 透過一個快指針和慢指針在一個 for 循環下完成兩個 for 循環的工作。
定義快慢指針：
- 快指針：尋找新陣列的元素，新陣列就是不含有目標元素的陣列
- 慢指針：指向更新 新陣列下標的位置
// 時間複雜度：O(n)
// 空間複雜度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
有序陣列的平方#
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
for (int i = 0, j = A.size() - 1; i <= j;) { // 注意這裡要i <= j，因為最後要處理兩個元素
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
};
滑動窗口#
所謂滑動窗口，就是不斷的調節子序列的起始位置和終止位置，從而得出我們想要的結果。
窗口就是滿足其和 ≥ s 的長度最小的 連續子陣列。
窗口的起始位置如何移動：如果當前窗口的值大於等於 s 了，窗口就要向前移動了（也就是該縮小了）。
窗口的結束位置如何移動：窗口的結束位置就是遍歷陣列的指針，也就是 for 循環裡的索引。
滑動窗口的精妙之處在於根據當前子序列和大小的情況，不斷調節子序列的起始位置。從而將 O (n^2) 暴力解法降為 O (n)。
長度最小的子陣列#
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
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 < subLength ? result : subLength;
sum -= nums[i++]; // 這裡體現出滑動窗口的精髓之處，不斷變更i（子序列的起始位置）
}
}
// 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列
return result == INT32_MAX ? 0 : result;
}
};
螺旋矩陣 2#
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定義一個二維陣列
int startx = 0, starty = 0; // 定義每循環一圈的起始位置
int loop = n / 2; // 每個圈循環幾次，例如n為奇數3，那麼loop = 1 只是循環一圈，矩陣中間的值需要單獨處理
int mid = n / 2; // 矩陣中間的位置，例如：n為3， 中間的位置就是(1，1)，n為5，中間位置為(2, 2)
int count = 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;
}
};