一、二分查找

1.1 二分查找母题

Leetcode 704

二分算法使用前提：

• 数组有序
• 元素不重复

二分算法中，对于区间的不同定义，决定着二分算法中代码不同写法。

写法一：定义 target 定义在一个左闭右闭的区间里面，即 [left, right]。

那么这时候代码需要注意：

• 循环 while (left <= right) 要使用 <= ，因为 left == right 是有意义的，所以使用 <=
• 代码 if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个 nums[middle] 一定不是 target，那么接下来要查找的左区间结束下标位置就是 middle - 1

代码如下：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + ((right - left) >> 1);  // 防止溢出if (nums[mid] > target) right = mid - 1;else if (nums[mid] < target) left = mid + 1;else return mid;}return -1;}
};

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

写法二：定义 target 定义在一个左闭右开的区间里 [left, right)。

那么这之后写代码需要注意：

• 循环 while (left < right)，这里使用 < ,因为 left == right 在区间 [left, right) 是没有意义的
• 代码 if (nums[middle] > target) 时 right 更新为 middle，因为当前 nums[middle] 不等于 target，去左区间继续寻找，而寻找区间是左闭右开区间，所以 right 更新为 middle，即：下一个查询区间不会去比较 nums[middle]

代码如下：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right) {int mid = left + ((right - left) >> 1);  // 防止溢出if (nums[mid] > target) right = mid;else if (nums[mid] < target) left = mid + 1;else return mid;}return -1;}
};

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

1.2 搜索插入位置

Leetcode 35

很明显使用二分查找，但是要处理一种特殊情况，即所查找元素不存在的时候，返回应该插入的位置。

对于插入元素，有四种插入位置：

• 目标值比数组中所有元素小，[0, -1]
• 目标值等于数组中的一个元素，return mid
• 目标值插入数组中的位置，[left, right], return right + 1
• 目标值比所有元素都大，return right + 1

这里要注意二分代码中，优先动的永远是右指针 right

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r) {int mid = l + ((r - l) >> 1);if (nums[mid] > target) r = mid - 1;else if (nums[mid] < target) l = mid + 1;else return mid;}return r + 1;}
};

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

1.3 在排序数组中查找元素的第一个和最后一个位置

Leetcode 34

这个题目有三种情况：

• 情况一：target 不在数组的大小范围内
• 情况二：target 在数组的大小范围内，但是 target 不在数组中
• 情况三：target 在数组的大小范围内且在数组中

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);if (leftBorder == -2 || rightBorder == -2) return {-1, -1}; // 情况一if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder -1}; // 情况三return {-1, -1}; // 情况二}// 寻找右边界int getRightBorder(vector<int> &nums, int target) {int l = 0, r = nums.size() - 1;int rightBorder = -2; // 初始值while (l <= r) {int mid = l + ((r - l) >> 1);if (nums[mid] > target) r = mid - 1;else l = mid + 1, rightBorder = l;}return rightBorder;}// 寻找左边界int getLeftBorder(vector<int> &nums, int target) {int l = 0, r = nums.size() - 1;int leftBorder = -2;while (l <= r) {int mid = l + ((r - l) >> 1);if (nums[mid] >= target) r = mid - 1, leftBorder = r; // 需要在 nums[mid] = target 的时候更新 leftBordelse l = mid + 1;}return leftBorder;}
};

1.4 x 的平方根

Leetcode 69

class Solution {
public:int mySqrt(int x) {int l = 0, r = x, res = -1;while (l <= r) {int mid = l + ((r - l) >> 1);if ((long long) mid * mid <= x)res = mid, l = mid + 1;else r = mid - 1;}return res;}
};

1.5 有效的完全平方数

Leetcode 367

class Solution {
public:bool isPerfectSquare(int num) {int l = 0, r = num;while (l <= r) {int mid = l + ((r - l) >> 1);if ((long long) mid * mid < num) l = mid + 1;else if ((long long) mid * mid > num) r = mid - 1;else return true;}return false;}
};

二、双指针

2.1 移除元素

Leetcode 27

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex ++ ) if (nums[fastIndex] != val)nums[slowIndex ++ ] = nums[fastIndex];return slowIndex;}
};

2.2 删除有序数组中的重复项

Leetcode 26

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1;for (int fast = 1; fast < nums.size(); fast ++ )if (nums[fast] != nums[fast - 1])nums[slow ++ ] = nums[fast];return slow;}
};

2.3 移动零

Leetcode 283

双指针操作，快指针指向待处理序列头部，慢指针指向当前已经处理好的序列尾部

快指针不断向右移动，每次右移指向非零元素时，则将快指针与慢指针指向的元素交换，同时往右移动慢指针

这里有两个性质：

• 慢指针左边元素均非零
• 快指针左边直到慢指针处的元素均为零

可以通过两次遍历，先将所有非零元素移到前面，然后将后面位置补 0 即可，但是这样做有违题意——移动零，不是 “补零”。

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;for (int fast = 0; fast < nums.size(); fast ++ )if (nums[fast]) swap(nums[slow ++ ], nums[fast]);}
};

2.4 比较含退格的字符串

Leetcode 844

class Solution {
public:void rebuild(string &s) {int slow = 0;for (char c : s) if (c == '#') {if (slow > 0) slow -- ;} else s[slow ++ ] = c;s.resize(slow);}bool backspaceCompare(string s, string t) {rebuild(s);rebuild(t);return s == t;}
};

2.5 有序数组的平方

Leetcode 977

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> res(nums.size(), 0);int l = 0, r = nums.size() - 1;int index = r;while (l <= r) if (-nums[l] > nums[r]) res[index -- ] = nums[l] * nums[l], l ++ ;else res[index -- ] = nums[r] * nums[r], r -- ;return res;}
};

三、滑动窗口

3.1 长度最小的子数组

Leetcode 209

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int res = INT32_MAX;int sum = 0, subLength = 0; // 窗口内的和、窗口长度for (int i = 0, j = 0; j < nums.size(); j ++ ) { // i表示窗口的起始位置sum += nums[j];while (sum >= target) {subLength = j - i + 1;res = min(res, subLength);sum -= nums[i ++ ]; // 移动窗口左边界}}return res == INT32_MAX ? 0 : res;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

时间复杂度为 $O(n)$，主要看数组中每一个元素的被操的次数，每个元素被操作两次，一次进入窗口、一处出窗口，时间复杂度为 $O(2n)$，即 $O(n)$。

3.2 水果成篮

Leetcode 904

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();unordered_map<int, int> cnt;int res = 0;for (int l = 0, r = 0; r < n; r ++ ) {cnt[fruits[r]] ++ ;while (cnt.size() > 2) {auto it = cnt.find(fruits[l]);it->second -- ;if (!it->second) cnt.erase(it);l ++ ;}res = max(res, r - l + 1);}return res;}
};

3.3 最小覆盖子串

Leetcode 76

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> tmap, smap;int correct = 0;string res = s + "initialize a max string";// 构建t中字符出现的字典for (auto c : t)tmap[c] ++ ;for (int l = 0, r = 0; r < s.size(); r ++ ) {smap[s[r]] ++ ;if (tmap[s[r]] >= smap[s[r]]) // 表示这是一次有效的添加correct ++ ;while (l < r && smap[s[l]] > tmap[s[l]])smap[s[l ++ ]] -- ;if (correct == t.size()) {if (r - l + 1 < res.size())res = s.substr(l, r - l + 1);}}return res == s + "initialize a max string" ? "" : res;}
};

四、螺旋矩阵

4.1 螺旋矩阵

Leetcode 54

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {vector<int> res;int n = matrix.size(), m = matrix[0].size();if (!n) return res;vector<vector<bool>> st(n, vector<bool>(m));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++ ) {res.push_back(matrix[x][y]);st[x][y] = true;int a = x + dx[d], b = y + dy[d];if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;}return res;}
};

4.2 螺旋矩阵Ⅱ

Leetcode 59

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int> (n, 0));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for (int i = 0, x = 0, y = 0, d = 0; i < n * n; i ++ ) {res[x][y] = i + 1;int a = x + dx[d], b = y + dy[d];if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]) {d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;}return res;}
};

4.3 螺旋矩阵Ⅲ

Leetcode 885

class Solution {
public:vector<vector<int>> spiralMatrixIII(int rows, int cols, int x, int y) {vector<vector<int>> res;int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};res.push_back({x, y});int d = 0, tot = rows * cols;for (int k = 1; res.size() < tot; k ++ ) // k：路径长度for (int i = 0; i < 2 && res.size() < tot; i ++ ) { // 每个长度会走两次for (int j = 0; j < k && res.size() < tot; j ++ ) { // 每一次长度都是kint a = x + dx[d], b = y + dy[d];if (a >= 0 && a < rows && b >= 0 && b < cols)res.push_back({a, b});x = a, y = b;}d = (d + 1) % 4;}return res;}
};

4.4 螺旋矩阵Ⅳ

Leetcode 2326

class Solution {
public:vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {vector<vector<int>> res(m, vector<int>(n, -1));int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};for (int i = 0, x = 0, y = 0, d = 0; i < n * m && head != nullptr; i ++ ) {res[x][y] = head->val;int a = x + dx[d], b = y + dy[d];if (a < 0 || a >= m || b < 0 || b >= n || res[a][b] != -1) {d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;head = head->next;}return res;}
};