LeetCode 常用代码模板总结
下标和循环次数的关系
左为 left 循环次数为 count， 那么右侧最后一个为 left+count-1 。
- 如果条件是
<那么就是<left+count。 右为right循环次数为count， 那么左边最后一个为right-count+1。 - 如果条件是
>那么就是>right-count。
数组中点
- 长度为n， 求中点，
- n是奇数， (n-1)/2， 比如n=3， 刚好是1
- n是偶数， (n-1)/2，
滑动到最后不同的
2025年12月2日19:59:10
- 使用while
- 先加加或者减减， 再使用while 判断， 比如right 位置， 如果直接使用while 进行循环， 那么第一次时 right = n-1，
nums[right] != nums[right + 1]right+1越界了， 因此要 先 right–， 再处理循环，
else {
// 刚好等于, 收集结果
ans.add(List.of(nums[i], nums[left], nums[right]));
// 平移指针
left++;
while (true) {
if (left >= right) {
break;
}
if (nums[left] != nums[left - 1]) {
break;
}
left++;
}
right--;
while (true) {
if (left >= right) {
break;
}
if (nums[right] != nums[right + 1]) {
break;
}
right--;
}
}
222…..24;
当前是 i 指向 2， 那么滑动到不是2的位置
- 先滑倒最后一个2:
while(nums[i]==nums[i+1]) i++， 最终停在不等的位置， 也就是最后一个2的位置，停在了最后一个i。 - 再后移一位
i++即可
[2-15三数之和](01 双指针/LeetCode 15 三数之和.md)
i也可以和i-1 判断，这需要i 初始时向后移一位；i>0确保了不会漏掉一开始的一种情况，j>i+1同理。
j从 i+1开始，如果不加 j>i+1的条件：nums[j]==nums[j-1] j=i+1时，如果nums[i]==nums[i+1]，j=i+1就会被跳过。
for(int i = 0;i<n;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j = i+1;j<n;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue;
[8-31下一个排列](01 双指针/LeetCode 31 下一个排列.md) right初始化 while中两个条件。
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int right = n-2;
while(right>=0&&nums[right]>=nums[right+1]){
right--;
}
快速找子数组
方法一：前缀和+hash_table。计算前缀和后，设某一位置为前缀和为sum，检验 sum-target 的合法性即可。
方法二：滑动窗口。只适用于正数。
子数组不重叠
使用left 来控制。[27-1477找两个和为目标值且不重复的子数组](02 滑动窗口/LeetCode 1477 找两个和为目标值且不重复的子数组.md)
size的返回值问题
unordered_set<int> hash_set;
hash_set.size()-1; 这里的size返回的是无符号数，减一
滑动直到 和 满足条件
要点：保证同一时间内 sum 中既有left 也有 right
int left = 0;
int sum = 0;
for(int i = 0;i<nums.size();i++){
sum+=nums[i] // 同一时间，sum中既有left 也有 i
while(sum>500){
sum-=nums[left] //2.减完后 left 后移，保证sum中有left
left++; //1. 先写变量控制条件
}
}
不重复
可以使用 unordered_map value:count
map[value]++
map[value]--
if(map[value]==0){
map.erase(value);
}
动态最值问题-单调队列
[26-239滑动窗口最大值](02 滑动窗口/LeetCode 239 滑动窗口最大值.md)
始终保持一个滑动窗口内的最大值和最小值。
比如维护最大值：当一个新元素进入时，前面比他小的元素不可能成为包含当前元素的窗口中的最大值，直接弹出即可
使用双端队列
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> deque_max; // 存储的是索引
vector<int> result;
for (int i = 0; i < nums.size(); ++i) {
// 移除队尾小于当前元素的所有元素
// 递减排序，队头为最大值
while (!deque_max.empty() && nums[deque_max.back()] < nums[i]) {
deque_max.pop_back();
}
deque_max.push_back(i);
// 移除不在当前滑动窗口中的元素
if (!deque_max.empty() && i-deque_max.front()+1 > k ) {
// 这里直接移除首个元素，因为这是队列，最开始的一定在队头。
// 队列里面不一定包含窗口内的所有元素。
deque_max.pop_front();
}
// 从第 k-1 个元素开始加入结果数组
if (i >= k - 1) {
result.push_back(nums[deque_max.front()]);
}
}
return result;
}
动态top k 问题
- 当数据范围较小时：可以使用计数排序， 直接构造一个数据范围的数组用来存储出现次数，再从小到大遍历并累加出现次数，直到累加和大于k。[6-2653滑动子数组的美丽值](02 滑动窗口/LeetCode 2653 滑动子数组的美丽值.md)
- 当数据会一直增加不删除时可以使用堆解决，比如求最大的k个元素，可以维护一个大小为k的小定堆（堆顶元素为这k个元素的最小值），后面插入的时候可以和堆顶元素比较，大于堆顶就先弹出后插入。
- 当数据既增加也删除时可以使用双堆：
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
//使用双堆求 len 窗口的第k小值。
class Solution{
public:
int k;
priority_queue<int> big_heap; //大顶堆 存前k小的元素，栈顶就是门槛。
priority_queue<int,vector<int>, greater<int>> small_heap; //小顶堆 存剩下的元素，栈顶就是剩下的最小的元素。
Solution(int val) : k(val) {}
void add(int num){
if(big_heap.size()<k){
big_heap.push(num);
}else{
//可能要查到小值里面，也可能插到大值里面。
if(num<big_heap.top()){
big_heap.push(num);
small_heap.push(big_heap.top());
big_heap.pop();
}else{
small_heap.push(num);
}
}
}
void remove(int num){
vector<int> buffer;
bool is_removed = false;
if(num<=big_heap.top()){
while(big_heap.top()>=num&&!is_removed){
if(big_heap.top()==num) is_removed = true;
buffer.push_back(big_heap.top());
big_heap.pop();
}
//最后一个是要删除的
buffer.pop_back();
for(int val: buffer){
big_heap.push(val);
}
buffer.clear();
//删除后左边就不是k个了， 因此要从右边拿一个过来。
int tmp = small_heap.top();
small_heap.pop();
big_heap.push(tmp);
}else{
while(small_heap.top()<=num&&!is_removed){
if(small_heap.top()==num) is_removed = true;
buffer.push_back(small_heap.top());
small_heap.pop();
}
//最后一个是要删除的
buffer.pop_back();
for(int val: buffer){
small_heap.push(val);
}
buffer.clear();
}
}
int get_small_k(){
return big_heap.top();
}
};
int main() {
Solution s(3);
int len = 4;
vector<int> stream = {4, 5, 8, 2,7,9,5,3};
for (int i = 0;i<len-1;i++) {
s.add(stream[i]);
cout << "3rd smallest after adding " << stream[i] << ": " << s.get_small_k() << endl;
}
cout<<"begin----------"<<endl;
for(int i = len-1;i<stream.size();i++){
s.add(stream[i]);
cout << "3rd smallest after adding " << stream[i] << ": " << s.get_small_k() << endl;
s.remove(stream[i-len+1]);
}
return 0;
}
- 为什么不用一个堆？（左边是小的，右边是大的）
- 插入时：可能查到最大堆里，也可能插到右边。没什么区别。
- 删除时：1. 删的元素在右边，没什么区别。 2. 删的元素在左边，需要右边找到最小元素加到左边。那么使用堆维护右边就可以直接取堆顶元素即可（当然插入右边时要进行调整：
log时间） - 总结：1. 单堆插入右边时无操作，左边删除时要找到右边最小元素
O(n)时间；2. 双堆插入右边时要调整log时间，左边删除时要找到右边最小元素，直接取栈顶即可。因此双堆更好尤其是这个窗口很大时，右边元素很多。
while
- 写循环先写 逻辑， 最后再写边界条件， 边界控制是为了让程序不出错或按照预期执行
[2-209长度最小的子数组](02 滑动窗口/LeetCode 209 长度最小的子数组.md)
试探性执行并检查结果。 这和 滑动直到不同的元素相似。
while(向后判断，试探性的检查执行之后的){
执行
}
while (sum - nums[left] >= target) { //检查执行之后的结果再决定是否进入循环。
//剪掉左边还能达标，就左移
sum -= nums[left]; //执行，这里的就是判断中的条件。
left++;
}
也可以不试探性检查，直接执行，最后的状态就会是不满足while条件的。
也就是说 sum应该是小于target的，大于的情况是“违法状态”，
//sum一开始是小数，所以while维护大数，至于答案的更新是在while里面还是 执行完while后是根据答案是小数还是大数。
while(sum>=target){
ans = min(ans,right-start+1);
sum-=nums[right];
right--;
}
sum不可以无脑和题意反着来，要根据初始状态来定，[3-713乘积小于k的子数组](02 滑动窗口/LeetCode 713 乘积小于 K 的子数组.md) 应该是和初始状态反着来。 prod一开始是小的，while 是排除大的情况；上面 209题 的sum 一开始也是小的，while 也是排除大的情况。只不过乘积收集的结果是小的，所以在while循环之后收集结果，而209收集的是大的，因此209的ans 更新在while循环里。
[11-1234替换子串得到平衡字符串](02 滑动窗口/LeetCode 1234 替换子串得到平衡字符串.md) 体会 while 的用法。
while 父子关系
while (t != null) {
parent = t; // 保存当前节点作为父节点
cmp = k.compareTo(t.key); // 比较 key 的大小
if (cmp < 0) {
t = t.left; // 如果 key 小于当前节点，移动到左子树
} else if (cmp > 0) {
t = t.right; // 如果 key 大于当前节点，移动到右子树
} else {
V oldValue = t.value; // 找到相同的 key
if (replaceOld || oldValue == null) {
t.value = value; // 更新节点值
}
return oldValue; // 返回旧值
}
}
father
while(判断 child){
father = child;
改变child
}
循环结束 使用father
while遍历时一个位置可能多次操作
[9-75颜色分类](01 双指针/LeetCode 75 颜色分类.md)
把i++放在合法的情况中，其他的情况各自处理。尽量使用if else 而非 多个if（可能会互相影响）。
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int p0 = 0;
int p2 = n - 1;
int i = 0;
while(i<=p2){
if(nums[i]==0){ //交换完nums_i 一定是 1 或 0 ，因此合法了
swap(nums[i],nums[p0]);
p0++;
i++;
}else if(nums[i]==2){
swap(nums[i],nums[p2]);
p2--;
}else{ //合法情况
i++;
}
}
}
};
递归和while
int child = heap.size()-1; //递归输入。
while(true){
if(child<=0) break; //break 为跳出递归
int parent = (child-1)/2;
if(heap[child]>heap[parent]) break; // 递归终止条件。
swap(heap[child],heap[parent]); // 本层要干的事情。
child = parent; // 在while的最底下更新递归的输入。
}
down 函数，递归函数输入为：开始的index。当比下层都大时递归终止；本层交换父子节点；最后在while 的最底下更新递归的输入 index。
void down(int index) {
while (true) {
int left_child = index * 2 + 1;
int right_child = left_child + 1;
int real_index = index;
if (left_child < heap.size() && heap[left_child] < heap[real_index]) {
real_index = left_child;
}
if (right_child < heap.size() && heap[right_child] < heap[real_index]) {
real_index = right_child;
}
if (index == real_index) {
break;
}
swap(heap[index], heap[real_index]);
index = real_index;
}
}
- 如果递归函数内部逻辑复杂， 我们可以增加入参。
class Heap{
public static void downAdjust(int[] a, int startIndex, int endIndex){
int parentIndex = startIndex;
int childIndex = parentIndex*2+1;
// 如果递归函数只有一个入参: parentIndex 会导致下面逻辑复杂, 这里使用两个入参
while(true){
if (childIndex>endIndex){
break;
}
if (childIndex+1<=endIndex&&a[childIndex]<a[childIndex+1]){
childIndex++;
}
if (a[parentIndex]>=a[childIndex]){
break;
}
int tmp = a[parentIndex];
a[parentIndex] = a[childIndex];
a[childIndex] = tmp;
parentIndex = childIndex;
childIndex = parentIndex*2+1;
}
}
public static int[] HeapSort(int[] a){
int n = a.length;
// 构建大顶堆, 从最后一个非叶节点向下调整
int lastNotLeafNodeIndex = n/2-1;
for (int i = lastNotLeafNodeIndex; i >=0 ; i--) {
downAdjust(a,i,n-1);
}
// 交换堆顶(a[0]) 和最后一个元素, 重新向下调整
for (int i = n-1; i >=0; i--) {
// i: 数组要确定的下标, 从n-1 开始确定
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
downAdjust(a,0,i-1);
}
return a;
}
}
[21-443压缩字符串](01 双指针/LeetCode 443 压缩字符串.md) 递归爆改while
设置-1
[24-1358包含所有三种字符的子串数目](02 滑动窗口/LeetCode 1358 包含所有三种字符的子串数目.md) 动规解法中，-1的设置巧妙地省去了很多判断。
在保持 res = left-(-1 ) 不变的情况下，迫使一开始也满足条件，只能初始化为 -1。
链表倒数第k
使用 count 作为步数（两个节点之间的跳跃）；
删除倒数第n个节点要找到倒数第n+1 节点：count>=n+1;
fast slow 都指向第一个节点，找倒数第k个节点 count>=k
途中slow 应该移动时 count时fs 的跳跃次数为2。
int count = 0;
while(fast->next!=nullptr){
fast = fast->next,count++;
if(count>=n+1){
slow = slow->next;
}
}
链表
- 如果选第一个时不能直接确定， 直接加上 fake_head 必要时加 fake_head
while（）条件 ：cur!=nullptr cur->next!=nullptr 取决于最后一个节点是否要进入循环执行。
- 2026-01-21， 很多情况不是算节点个数，而是步数(链表指针数)
链表中间节点
- 中间和中间偏后
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
- 中间和中间偏前， fast初始化就向前一步
ListNode slow = head;
ListNode fast = head.next;
while (fast!=null&&fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
对齐
- 自己加
aaa bbb ccc截取其中的字符串，因为数据不齐，因此可以选择在前面补。
s = ' '+s; //在前面加一个空格。
n = s.size();
int i = n-1,j = n-1;
while(i>=0){
if(s[i]!=' '&&s[i+1]==' ') j = i;
if(s[i]!=' '&&s[i-1]==' ') res.push_back(s.substr(i,j-i+1));
i--;
}
- 设置初始值：通过一个装有abc的数组要得到字符串
a b c设置初始这为a 遍历加空格和下一个。
string res_s = res[0];
for(int i = 1;i<res.size();i++){
res_s+=' ';
res_s+=res[i];
}
- 两个数据对比，但两个数据长度不一；假返回或设置初始值 [17-165比较版本号](01 双指针/LeetCode 165 比较版本号.md) 假返回的思路通过设置初始值实现。
找最小值， 可能为null
- 堆的向下调整
- 先设置默认值， 然后逐步更新
private void down(int index){
int n = heap.size();
while (true) {
if (index>=n) {
break;
}
// 判断要不要交换, 找到要交换的下标
int leftChildIndex = index*2+1;
int rightChildIndex = index*2+2;
int realSwapIndex = index;
if (leftChildIndex<n) {
realSwapIndex = heap.get(realSwapIndex)<=heap.get(leftChildIndex)?realSwapIndex:leftChildIndex;
}
if (rightChildIndex<n) {
realSwapIndex = heap.get(realSwapIndex)<=heap.get(rightChildIndex)?realSwapIndex:rightChildIndex;
}
// swap
swap(index, realSwapIndex);
// 更新 index
if (realSwapIndex==index) {
break;
}else{
index = realSwapIndex;
}
}
}
前缀和
记得加0
map.put(0,1)
递归转while
二叉树中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
dfs(root, list);
return list;
}
private void dfs(TreeNode root,List list){
if (root==null) {
return;
}
dfs(root.left, list);
list.add(root.val);
dfs(root.right, list);
}
}
- 转为递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 迭代算法, 使用栈模拟递归调用
List<Integer> list= new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
TreeNode cur = root;
while (true) {
if (cur==null&&deque.isEmpty()) {
break;
}
// 调用 root.left, 入栈
if (cur!=null) {
deque.push(cur);
cur = cur.left;
}else{
cur = deque.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
- 本质是修改传参， 这里是修改
cur， - 关于什么时候入栈， 什么时候出栈，
- 当修改传参之前要考虑是否要入栈出栈
A+B 变为 B+A
A+B -> rev(A)+rev(B) - >rev[rev(A)+rev(B)] = B+A
避开第一次
public class Solution {
public boolean hasCycle(ListNode head) {
// slow 和fast是当前位置,
ListNode slow = head;
ListNode fast = head;
while (slow!=null&&fast!=null&&fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
// 我们检查当前位置是否相遇, 不在while内第一条检查,在while最后一条前检查
if (slow==fast) {
return true;
}
}
return false;
}
}
复杂情况- 先设置为默认值， 再修改
- 合并链表
while (a != null || b != null) {
ListNode temp = a;
if (b != null) {
if (temp == null) {
temp = b;
} else {
temp = a.val < b.val ? a : b;
}
}
if (temp == a) {
a = a.next;
} else {
b = b.next;
}
cur.next = temp;
cur = cur.next;
}
- 合并， 先设置为默认值， 再赋值
// 合并 n / (2 * step)+1 次, 剩下的可能不到 2 * step, 但是可能大于一个step, 因此需要1次,
for (int i = 0; i < n / (2 * step)+1; i++) {
ListNode first = cur.next;
cur.next = null;
ListNode secend = null;
ListNode other = null;
ListNode firstEnd = tryStep(first, step - 1);
if (firstEnd != null && firstEnd.next != null) {
secend = firstEnd.next;
firstEnd.next = null;
}
ListNode secendEnd = tryStep(secend, step - 1);
if (secendEnd != null) {
other = secendEnd.next;
secendEnd.next = null;
}
ListNode[] arr = merge(first, secend);
cur.next = arr[0];
arr[1].next = other;
cur = arr[1];
}