【双指针】基础知识

为何学习双指针算法效率高把嵌套循环变成单层循环时间复杂度从 O (n²) 降到 O (n)数据量越大优势越明显空间省不需要额外开辟数组、哈希表等空间空间复杂度 O (1)逻辑简单不用复杂的递归或数学推导只要想清楚 “两个指针怎么动”代码就能写出来。以下是几道简单但典型的双指针算法的题目左右指针LeetCode 167. 两数之和 II - 输入有序数组题目描述在有序数组中找出两个数使它们的和为 target。返回这两个数的下标。解法思路如果暴力双层循环时间复杂度是 O(N^2)。但数组是有序的我们可以用左右指针夹击left 指向最小值最左边right 指向最大值最右边。计算 sum nums[left] nums[right]。如果 sum target找到了如果 sum target说明两数之和太小了需要增大于是 left。如果 sum target说明两数之和太大了需要减小于是 right–。int*twoSum(int*numbers,intnumbersSize,inttarget,int*returnSize){intleft0;intrightnumbersSize-1;int*ans(int*)malloc(sizeof(int)*2);*returnSize2;while(leftright){intsumnumbers[left]numbers[right];if(sumtarget){ans[0]left1;// 题目要求下标从 1 开始ans[1]right1;returnans;}elseif(sumtarget){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*slowhead;structListNode*fasthead;// fast 走到头或者 fast 的下一步走到头就结束while(fast!NULLfast-next!NULL){slowslow-next;// 慢指针走一步fastfast-next-next;// 快指针走两步}returnslow;}距离差指针LeetCode 19. 删除链表的倒数第 N 个结点题目描述给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。解法思路如果先遍历求长度再遍历去删同样是两遍扫描。双指针的绝妙之处在于制造固定的距离差。定义一个虚拟头结点 dummy重要技巧防止删除头结点。让 fast 指针先走 n 1 步。然后 slow 从 dummy 出发与 fast 一起同步向前走。当 fast 走到 NULL 时slow 刚好停在倒数第 n 个节点的前一个节点此时直接执行删除操作即可。structListNode*removeNthFromEnd(structListNode*head,intn){structListNode*dummy(structListNode*)malloc(sizeof(structListNode));dummy-nexthead;structListNode*fastdummy;structListNode*slowdummy;// fast 先走 n1 步for(inti0;in;i){fastfast-next;}// 两人一起走while(fast!NULL){fastfast-next;slowslow-next;}// 此时 slow 位于倒数第 n 个的前一个structListNode*tempslow-next;slow-nextslow-next-next;free(temp);structListNode*newHeaddummy-next;free(dummy);returnnewHead;}最后双指针算法看似变化多端但核心算法只有一个不要轻易申请空间试着在原数据结构上通过移动改变指针的规则来寻找答案