上一节讲了时间复杂度和空间复杂度这一节来学一个在面试和竞赛中出场率极高的技巧——双指针。名字听起来很玄乎其实思路非常简单用两个变量指针在数组上移动通过它们的配合来解决问题。1. 什么是双指针「指针」在这里不是 C 语言里的内存地址而是一个形象的说法——它就是数组的下标索引。双指针就是同时用两个下标变量来遍历数组。双指针有两种常见模式快慢指针两个指针从同一端出发速度不同左右指针两个指针分别从数组两端出发向中间靠拢下面分别来看。2. 快慢指针2.1 核心思路快慢指针就像两个人在跑步——一个跑得快一个跑得慢。通过观察它们的位置关系可以发现一些有用的性质。2.2 经典问题删除有序数组中的重复项题目给定一个升序排列的数组nums原地删除重复元素使每个元素只出现一次返回新数组的长度。比如输入[1, 1, 2]处理后数组变成[1, 2, _]返回 2。思路用一个「慢指针」slow标记当前不重复元素应该存放的位置用一个「快指针」fast去扫描整个数组当nums[fast] ! nums[slow]时说明遇到了新的不重复元素把它放到slow 1的位置int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }过程演示以[1, 1, 2, 2, 3]为例初始: slow0, fast1 第 1 轮: nums[1]1 nums[0]1跳过 → slow0, fast2 第 2 轮: nums[2]2 ! nums[0]1slow赋值 → [1,2,2,2,3], slow1, fast3 第 3 轮: nums[3]2 nums[1]2跳过 → slow1, fast4 第 4 轮: nums[4]3 ! nums[1]2slow赋值 → [1,2,3,2,3], slow2, fast5 结束返回 slow1 3时间复杂度 O(n)空间复杂度 O(1)非常高效。2.3 经典问题判断链表是否有环虽然这道题用的是链表但快慢指针的思想完全一样bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }如果链表有环快指针迟早会「追上」慢指针。如果没有环快指针会先到达末尾。3. 左右指针3.1 核心思路左右指针是两个指针分别指向数组的头和尾然后根据条件向中间收缩。这种模式在有序数组上特别好用。3.2 经典问题两数之和有序数组版本题目给定一个升序数组nums和一个目标值target找到两个数使它们的和等于target返回它们的下标。比如输入nums [2, 7, 11, 15]target 9返回[0, 1]因为 2 7 9。思路左指针left指向数组开头右指针right指向数组末尾计算sum nums[left] nums[right]如果sum target找到了返回结果如果sum target说明和太小了left让和变大如果sum target说明和太大了right--让和变小vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return {left, right}; } else if (sum target) { left; } else { right--; } } return {}; }为什么这个方法有效因为数组是有序的。left右移会让和变大right左移会让和变小。通过不断调整两个指针最终会收敛到正确答案。时间复杂度 O(n)。3.3 经典问题盛最多水的容器题目给定n个非负整数height[0], height[1], ..., height[n-1]每个数代表坐标点(i, height[i])处的一条垂线。找两条线使得它们与 x 轴围成的容器能盛最多的水。思路左右指针分别指向头尾面积 min(height[left], height[right]) * (right - left)移动较短的那一边的指针因为移动较长的那边不可能让面积变大int maxArea(vectorint height) { int left 0, right height.size() - 1; int result 0; while (left right) { int area min(height[left], height[right]) * (right - left); result max(result, area); if (height[left] height[right]) { left; } else { right--; } } return result; }4. 双指针的使用场景总结模式适用场景典型题目快慢指针检测环、去重、找中点有序数组去重、链表环检测左右指针有序数组上的搜索、求和两数之和、盛水容器、三数之和判断是否能用双指针的关键数据是否有序或者问题是否满足单调性。如果移动一个指针能让结果朝着某个确定方向变化双指针大概率可行。5. 练习建议刚接触双指针不要急着刷难题先把上面几道经典题手动模拟一遍画出每一步指针的位置变化。等你对指针移动的感觉建立起来之后再去做变体题就会顺畅很多。推荐的练习顺序有序数组去重LeetCode 26两数之和 - 有序数组LeetCode 167盛最多水的容器LeetCode 11三数之和LeetCode 15——左右指针的进阶应用下一节我们会学习链表反转同样是面试高频考点。
【算法】小白也能懂 · 第 2 节：数组双指针技巧（快慢指针、左右指针）
发布时间：2026/7/16 4:49:24
上一节讲了时间复杂度和空间复杂度这一节来学一个在面试和竞赛中出场率极高的技巧——双指针。名字听起来很玄乎其实思路非常简单用两个变量指针在数组上移动通过它们的配合来解决问题。1. 什么是双指针「指针」在这里不是 C 语言里的内存地址而是一个形象的说法——它就是数组的下标索引。双指针就是同时用两个下标变量来遍历数组。双指针有两种常见模式快慢指针两个指针从同一端出发速度不同左右指针两个指针分别从数组两端出发向中间靠拢下面分别来看。2. 快慢指针2.1 核心思路快慢指针就像两个人在跑步——一个跑得快一个跑得慢。通过观察它们的位置关系可以发现一些有用的性质。2.2 经典问题删除有序数组中的重复项题目给定一个升序排列的数组nums原地删除重复元素使每个元素只出现一次返回新数组的长度。比如输入[1, 1, 2]处理后数组变成[1, 2, _]返回 2。思路用一个「慢指针」slow标记当前不重复元素应该存放的位置用一个「快指针」fast去扫描整个数组当nums[fast] ! nums[slow]时说明遇到了新的不重复元素把它放到slow 1的位置int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow]) { slow; nums[slow] nums[fast]; } } return slow 1; }过程演示以[1, 1, 2, 2, 3]为例初始: slow0, fast1 第 1 轮: nums[1]1 nums[0]1跳过 → slow0, fast2 第 2 轮: nums[2]2 ! nums[0]1slow赋值 → [1,2,2,2,3], slow1, fast3 第 3 轮: nums[3]2 nums[1]2跳过 → slow1, fast4 第 4 轮: nums[4]3 ! nums[1]2slow赋值 → [1,2,3,2,3], slow2, fast5 结束返回 slow1 3时间复杂度 O(n)空间复杂度 O(1)非常高效。2.3 经典问题判断链表是否有环虽然这道题用的是链表但快慢指针的思想完全一样bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }如果链表有环快指针迟早会「追上」慢指针。如果没有环快指针会先到达末尾。3. 左右指针3.1 核心思路左右指针是两个指针分别指向数组的头和尾然后根据条件向中间收缩。这种模式在有序数组上特别好用。3.2 经典问题两数之和有序数组版本题目给定一个升序数组nums和一个目标值target找到两个数使它们的和等于target返回它们的下标。比如输入nums [2, 7, 11, 15]target 9返回[0, 1]因为 2 7 9。思路左指针left指向数组开头右指针right指向数组末尾计算sum nums[left] nums[right]如果sum target找到了返回结果如果sum target说明和太小了left让和变大如果sum target说明和太大了right--让和变小vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return {left, right}; } else if (sum target) { left; } else { right--; } } return {}; }为什么这个方法有效因为数组是有序的。left右移会让和变大right左移会让和变小。通过不断调整两个指针最终会收敛到正确答案。时间复杂度 O(n)。3.3 经典问题盛最多水的容器题目给定n个非负整数height[0], height[1], ..., height[n-1]每个数代表坐标点(i, height[i])处的一条垂线。找两条线使得它们与 x 轴围成的容器能盛最多的水。思路左右指针分别指向头尾面积 min(height[left], height[right]) * (right - left)移动较短的那一边的指针因为移动较长的那边不可能让面积变大int maxArea(vectorint height) { int left 0, right height.size() - 1; int result 0; while (left right) { int area min(height[left], height[right]) * (right - left); result max(result, area); if (height[left] height[right]) { left; } else { right--; } } return result; }4. 双指针的使用场景总结模式适用场景典型题目快慢指针检测环、去重、找中点有序数组去重、链表环检测左右指针有序数组上的搜索、求和两数之和、盛水容器、三数之和判断是否能用双指针的关键数据是否有序或者问题是否满足单调性。如果移动一个指针能让结果朝着某个确定方向变化双指针大概率可行。5. 练习建议刚接触双指针不要急着刷难题先把上面几道经典题手动模拟一遍画出每一步指针的位置变化。等你对指针移动的感觉建立起来之后再去做变体题就会顺畅很多。推荐的练习顺序有序数组去重LeetCode 26两数之和 - 有序数组LeetCode 167盛最多水的容器LeetCode 11三数之和LeetCode 15——左右指针的进阶应用下一节我们会学习链表反转同样是面试高频考点。
