算法 - 二分法 / 双指针 / 三指针 / 滑动窗口

🍺 二分法

🍻 旋转数组

🥂 33. 搜索旋转排序数组 [旋转数组] [目标值] (二分法)

class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;// 二分法while (left <= right) {int mid = left + (right - left) / 2;// 先判断找到目标了没if (nums[mid] == target) return mid;// 再继续左右两边找, nums[mid] < nums[0] 说明 mid 在右边if (nums[mid] <= nums[0]) {// 此时 target 处于右右边if (nums[mid] < target && target <= nums[n - 1]) {left = mid + 1;         // 右右} else {right = mid - 1;        // 右左}} else {if (nums[0] <= target && target < nums[mid]) {right = mid - 1;        // 左左} else {left = mid + 1;         // 左右}}}return -1;}
};

🍻 元素边界

🥂 34. 在排序数组中查找元素的第一个和最后一个位置 [有序数组] > [元素边界] > (二分法)

// [有序数组] > [查找元素边界] > (二分法)
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = find_l(nums, target);int right = find_r(nums,target);return {left, right};}// 二分法查找左边界 [left, right]int find_l(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {// [left, mid - 1] [mid] [mid + 1, right]int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}// left = 3, right = 3 - 1 = 2if (0 <= left && left < n && nums[left] == target) {return left;}return -1;}// 二分法查找右边界 [left, right]int find_r(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {// [left, mid - 1] [mid] [mid + 1, right]int mid = left + (right - left) / 2;if (nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}}// right = 4, left = 4 + 1 = 5if (0 <= right && right < n && nums[right] == target) {return right;}return -1;}
};

🥂 81. 搜索旋转排序数组Ⅱ [旋转数组] [有重] [目标值] (二分法)

class Solution {
public:bool search(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;// 二分法while (left <= right) {// 判断是否存在int mid = left + (right - left) / 2;if (nums[mid] == target) return true;// 去除重复元素if (nums[mid] == nums[left]) {left++;continue;}if (nums[mid] == nums[right]) {right--;continue;}// 防止卡住, 区分不出左右if (nums[mid] < nums[0]) {  // 右// 再判断 target 在右边的左边还是右边 [left, mid-1][mid][mid+1, right]if (nums[mid] < target && target <= nums[n - 1]) {left = mid + 1;     // 右右} else {right = mid - 1;    // 右左}} else {                    // 左// 再判断 target 在左边的左边还是右边 [left, mid-1][mid][mid+1, right]if (nums[0] <= target && target < nums[mid]) {right = mid - 1;    // 左左} else {left = mid + 1;     // 左右}}}return false;}
};

🥂 153. 寻找旋转排序数组中的最小值 [旋转数组] [最小值] (二分法)

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;// 二分法 [0, n-1]while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < nums[right]) {right = mid;} else if (nums[mid] > nums[right]) {left = mid + 1;} else {right--;}}return nums[left];}
};

🍺 双指针

🍻 元素合并

🥂 21. 合并两个有序链表 [有序链表] [合并] (双指针) (归并)

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 虚拟头节点, 当前节点指向虚拟头节点ListNode* dummy = new ListNode(-1), * cur = dummy;// 双指针ListNode* p1 = list1, * p2 = list2;while (p1 != nullptr && p2 != nullptr) {if (p1->val < p2->val) {cur->next = p1;p1 = p1->next;} else {cur->next = p2;p2 = p2->next;}cur = cur->next;}// 剩下的直接拼上if (p1 != nullptr) cur->next = p1;if (p2 != nullptr) cur->next = p2;return dummy->next;}
};

🍻 元素交换

🥂 LCR 139. 训练计划 I [数组] [元素交换] (双指针)

class Solution {
public:vector<int> trainingPlan(vector<int>& actions) {int n = actions.size();if (n <= 1) return actions;// 定义双指针，一个指向头，一个指向尾int left = 0, right = n - 1;             while (left < right) {// 依次移动，找到数时暂停while (left < right && actions[left] % 2 == 1) {left++;}while (left < right && actions[right] % 2 == 0) {right--;}std::swap(actions[left], actions[right]);}return actions;}
};

🍻 元素相交

🥂 142. 环形链表II [链表] > [环] > (双指针)

// [链表] > [环] > (双指针)
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* dummy = new ListNode(-1);dummy->next = head;ListNode* fast = dummy, * slow = dummy;// 满指针走一步, 快指针走两步, 判断有无环while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;// 如果相遇, 则让满指针从头开始走, 两者同步移动if (fast == slow) {fast = dummy;while (fast != slow) {slow = slow->next;fast = fast->next;}return fast;}}return nullptr;   }
};

🥂 160. 相交链表 [链表] > [相交] > (双指针)

// [链表] > [相交] > (双指针)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 双指针ListNode *p1 = headA, *p2 = headB;// A 走到 nullptr 后接着走 B, B 走到 nullptr 后接着走 A// 当 p1 == p2 的地方就是相交的地方while (p1 != p2) {if (p1 == nullptr) p1 = headB;else p1 = p1->next;if (p2 == nullptr) p2 = headA;else p2 = p2->next;}return p1;}
};

🍻 面积

🥂 11. 盛最多水的容器 [数组] [面积] (双指针)

class Solution {
public:int maxArea(vector<int>& height) {// 双指针int left = 0, right = height.size() - 1;// 最大面积, 当前面积int res = 0, cur = 0;// 缩小区域while (left < right) {cur = min(height[left], height[right]) * (right - left);res = max(res, cur);// 哪一边比较短, 移动哪一边if (height[left] < height[right]) {left++;} else {right--;}}return res;}
};

🥂 42. 接雨水 [数组] [面积] (双指针)

class Solution {
public:int trap(vector<int>& height) {// 左边边界, 右边边界, 最边上存不了水int left = 0, right = height.size() - 1;// 左边最大值, 右边最大值int left_max = height[left], right_max = height[right];// 当前装水量, 总装水量int cur = 0, res = 0;while (left <= right) {left_max = max(left_max, height[left]);right_max = max(right_max, height[right]);if (left_max < right_max) {// 左指针的leftMax比右指针的rightMax矮// 说明：左指针的右边至少有一个板子 > 左指针左边所有板子// 那么可以计算左指针当前列的水量：左边最大高度-当前列高度res += left_max - height[left];left++;} else {res += right_max - height[right];right--;}}return res;}
};

🥂 其他

🥂 31. 下一个排列 [数组] [排列] (双指针) (推导)

class Solution {
private:int flag = 0;   // 设置一个标志位, 代表找到当前排列了
public:void nextPermutation(vector<int>& nums) {int n = nums.size();// 从后往前找, 找到第一个 nums[i] < nums[j] 的地方int i = n - 2, j = n - 1;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 此时不是最后一个排列if (i >= 0) {// 找到一个比 nums[i] 大的第一个元素while (j > i && nums[j] <= nums[i]) {j--;}// 交换两者swap(nums[i], nums[j]);// 再将剩余部分逆转, 把降序变为升序reverse(nums.begin() + i + 1, nums.end());} else {// 如果是最后一个排列reverse(nums.begin(), nums.end());}return;}
};

🍺 三指针

🍻 链表反转

🥂 25. K 个一组翻转链表 [链表] [分组反转] (三指针)

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {// 虚拟头节点ListNode* dummy = new ListNode(-1);     dummy->next = head;// 前置节点和后置节点ListNode* pre = dummy, * end = dummy;// 每次翻转 K 个节点while (end->next != nullptr) {for (int i = 0; i < k && end != nullptr; ++i) {end = end->next;}if (end == nullptr) break;// [pre] > [start] > [2] > [end] | [next] [5]ListNode* start = pre->next, * next = end->next;end->next = nullptr;// [pre] > [end] > [2] > [start] | [next] [5]pre->next = reverse(start);// [pre] > [end] > [2] > [start] > [next] [5]start->next = next;pre = start;end = start;}return dummy->next;}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] > [next]ListNode* pre = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* next = cur->next;// [pre] < [cur] | [next]cur->next = pre;// [N] < [pre] | [cur]pre = cur;cur = next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;} 
};

🥂 92. 反转链表II [链表] [反转] (三指针)

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummy = new ListNode(-1);dummy->next = head;// 四个指针分别指向 pre start end next// [1] > [pre] > [start] > [4] > [5] > [end] > [next]ListNode* pre = dummy, * end = dummy;for (int i = 0; i < left - 1; ++i) pre = pre->next;cout << pre->val;for (int j = 0; j < right; ++j) end = end->next;ListNode* start = pre->next, * next = end->next;// [1] > [pre] > [start] > [4] > [5] > [end] | [next]end->next = nullptr;// [1] > [pre] > [end] > [5] > [4] > [start] | [next]pre->next = reverse(start);// [1] > [pre] > [end] > [5] > [4] > [start] > [next]start->next = next;return dummy->next;}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] > [next]ListNode* pre = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* next = cur->next;// [pre] < [cur] | [next]cur->next = pre;// [N] < [pre] | [cur]pre = cur;cur = next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;}
};

🥂 206. 反转链表 [链表] [反转] (三指针)

class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(head);}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] > [next]ListNode* pre = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* next = cur->next;// [pre] < [cur] | [next]cur->next = pre;// [N] < [pre] | [cur]pre = cur;cur = next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;}
};

🍻 快速排序

🥂 215. 数组中的第K个最大元素 [数组] [第K大元素] (三指针) (快速排序)

class Solution {
private:int target; // 目标索引, 第 n-k 小int res;    // 目标值
public:int findKthLargest(vector<int>& nums, int k) {// 快速排序, 每次可以确定好一个元素的位置, 当索引为 k 时, 代表找到int n = nums.size();// 第 k 大就是第 n - k 小target = n - k;// 开始快排quickSort(nums, 0, n - 1);return res;}// 快排 [left, right]void quickSort(vector<int>& nums, int left, int right) {if (left > right) return;// 只剩一个元素if (left == right && left == target) {res = nums[target];return;}// 先获取一个哨兵, 将数组分为小于它的部分和大于它的部分vector<int> edge = part(nums, left, right);// 如果 target 在左右边界之间, 则找到if (edge[0] <= target && target <= edge[1]) {res = nums[target];return;}// 继续递归quickSort(nums, left, edge[0] - 1);quickSort(nums, edge[1] + 1, right);}// 分隔, 三指针, 这里返回相同元素的左右边界是为了去重vector<int> part(vector<int>& nums, int left, int right) {int pivot_idx = rand() % (right - left + 1) + left;int pivot = nums[pivot_idx];// [pivot]  [1]  [2]  [3]  [4]//  L/LP    CP                  RP swap(nums[pivot_idx], nums[left]);// 设置三个指针, 分别指向小于 pivot 的元素, 当前元素, 大于 pivot 的元素int curp = left + 1, leftp = left, rightp = right + 1;// 还没走到尽头, rightp 始终是指向大于 pivot 元素的while (curp < rightp) {if (nums[curp] < pivot) {           // 小于哨兵leftp++;swap(nums[curp], nums[leftp]);curp++;} else if (nums[curp] > pivot) {    // 大于哨兵rightp--;swap(nums[curp], nums[rightp]);} else {                            // 相等, 什么也不做curp++;}}// 最后 leftp 指向的内容肯定是最后一个小于 pivot 的, 它与 pivot 交换swap(nums[left], nums[leftp]);// 返回等于 pivot 的左边界和右边界 [小于] [pivot] [大于]return {leftp, rightp - 1};}
};

🥂 912. 排序数组 [数组] [排序] (三指针) (快速排序)

class Solution {
public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();quickSort(nums, 0, n - 1);return nums;}// 快排 [left, right]void quickSort(vector<int>& nums, int left, int right) {// 只剩一个元素, 就不用排了if (left > right) return;// 先获取一个哨兵, 将数组分为小于它的部分和大于它的部分vector<int> edge = part(nums, left, right);// 继续递归quickSort(nums, left, edge[0] - 1);quickSort(nums, edge[1] + 1, right);}// 分隔, 三指针, 这里返回相同元素的左右边界是为了去重vector<int> part(vector<int>& nums, int left, int right) {int pivot_idx = rand() % (right - left + 1) + left;int pivot = nums[pivot_idx];// [pivot]  [1]  [2]  [3]  [4]//  L/LP    CP                  RP swap(nums[pivot_idx], nums[left]);// 设置三个指针, 分别指向小于 pivot 的元素, 当前元素, 大于 pivot 的元素int curp = left + 1, leftp = left, rightp = right + 1;// 还没走到尽头, rightp 始终是指向大于 pivot 元素的while (curp < rightp) {if (nums[curp] < pivot) {           // 小于哨兵leftp++;swap(nums[curp], nums[leftp]);curp++;} else if (nums[curp] > pivot) {    // 大于哨兵rightp--;swap(nums[curp], nums[rightp]);} else {                            // 相等, 什么也不做curp++;}}// 最后 leftp 指向的内容肯定是最后一个小于 pivot 的, 它与 pivot 交换swap(nums[left], nums[leftp]);// 返回等于 pivot 的左边界和右边界 [小于] [pivot] [大于]return {leftp, rightp - 1};}
};

🍺 滑动窗口

🍻 子串

🥂 3. 无重复字符的最长子串 [字符串] [子串] (滑动窗口)

class Solution {
private:unordered_map<char, int> umap;      // 滑动窗口int res = 0;                        // 存放结果
public:int lengthOfLongestSubstring(string s) {int n = s.size();int left = 0, right = 0;        // 窗口边界while (right < n) {char cur_r = s[right++];    // 取当前字符串umap[cur_r]++;              // 更新窗口内容// 判断是否该缩小窗口while (umap[cur_r] > 1) {char cur_l = s[left++];umap[cur_l]--;}// 此时已经没有重复元素出现 [left, right)res = max(res, right - left);}return res;}
};

🍻 区间和

🥂 1423. 可获得的最大点数 [数组] > [区间外最大值] > [区间内最小值] > (定长滑动窗口)

// [数组] > [区间外最大值] > [区间内最小值] > (定长滑动窗口)
class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {int n = cardPoints.size();int windowSize = n - k;// [0, n-k] 的区间和int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);int min_val = sum;          // 窗口的最小值// 移动for (int i = 0; i < n - windowSize; ++i) {int left = i, right = i + windowSize;sum += cardPoints[right] - cardPoints[left];min_val = min(min_val, sum);}return accumulate(cardPoints.begin(), cardPoints.end(), 0) - min_val;}
};