企业官网建设流程全解析

为何学习双指针算法

1. 效率高：把嵌套循环变成单层循环，时间复杂度从 O (n²) 降到 O (n)，数据量越大，优势越明显

2. 空间省：不需要额外开辟数组、哈希表等空间，空间复杂度 O (1)

3. 逻辑简单：不用复杂的递归或数学推导，只要想清楚 “两个指针怎么动”，代码就能写出来。

以下是几道简单但典型的双指针算法的题目

左右指针

LeetCode 167. 两数之和 II - 输入有序数组
题目描述：在有序数组中找出两个数，使它们的和为 target。返回这两个数的下标。

解法思路：
如果暴力双层循环，时间复杂度是 O(N^2)。但数组是有序的！我们可以用左右指针夹击：

1. left 指向最小值（最左边），right 指向最大值（最右边）。
2. 计算 sum = nums[left] + nums[right]。
3. 如果 sum == target，找到了！
4. 如果 sum < target，说明两数之和太小了，需要增大，于是 left++。
5. 如果 sum > target，说明两数之和太大了，需要减小，于是 right–。

int*twoSum(int*numbers,intnumbersSize,inttarget,int*returnSize){intleft=0;intright=numbersSize-1;int*ans=(int*)malloc(sizeof(int)*2);*returnSize=2;while(left<right){intsum=numbers[left]+numbers[right];if(sum==target){ans[0]=left+1;// 题目要求下标从 1 开始ans[1]=right+1;returnans;}elseif(sum<target){left++;// 和太小，左指针右移}else{right--;// 和太大，右指针左移}}ans[0]=-1;ans[1]=-1;returnans;}

快慢指针

LeetCode 876. 链表的中间结点
题目描述：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

解法思路：
常规解法是遍历两遍：第一遍算长度，第二遍找中点。但用双指针，只需遍历一遍。
我们定义两个指针 slow 和 fast，初始都指向头节点 head。slow 每次走 1 步，fast 每次走 2 步。
当 fast 走到链表末尾时，slow 刚好走到中点。

structListNode*middleNode(structListNode*head){structListNode*slow=head;structListNode*fast=head;// fast 走到头，或者 fast 的下一步走到头，就结束while(fast!=NULL&&fast->next!=NULL){slow=slow->next;// 慢指针走一步fast=fast->next->next;// 快指针走两步}returnslow;}

距离差指针

LeetCode 19. 删除链表的倒数第 N 个结点
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解法思路：
如果先遍历求长度，再遍历去删，同样是两遍扫描。双指针的绝妙之处在于：制造固定的距离差。

1. 定义一个虚拟头结点 dummy（重要技巧，防止删除头结点）。
2. 让 fast 指针先走 n + 1 步。
3. 然后 slow 从 dummy 出发，与 fast 一起同步向前走。
4. 当 fast 走到 NULL 时，slow 刚好停在倒数第 n 个节点的前一个节点，此时直接执行删除操作即可。

structListNode*removeNthFromEnd(structListNode*head,intn){structListNode*dummy=(structListNode*)malloc(sizeof(structListNode));dummy->next=head;structListNode*fast=dummy;structListNode*slow=dummy;// fast 先走 n+1 步for(inti=0;i<=n;i++){fast=fast->next;}// 两人一起走while(fast!=NULL){fast=fast->next;slow=slow->next;}// 此时 slow 位于倒数第 n 个的前一个structListNode*temp=slow->next;slow->next=slow->next->next;free(temp);structListNode*newHead=dummy->next;free(dummy);returnnewHead;}

最后

双指针算法看似变化多端，但核心算法只有一个，不要轻易申请空间，试着在原数据结构上通过移动改变指针的规则来寻找答案