当前位置：首页 > news >正文

【算法】小白也能懂 · 第 2 节：数组双指针技巧（快慢指针、左右指针）

news 2026/5/9 12:37:47

上一节讲了时间复杂度和空间复杂度，这一节来学一个在面试和竞赛中出场率极高的技巧——双指针。名字听起来很玄乎，其实思路非常简单：用两个变量（指针）在数组上移动，通过它们的配合来解决问题。

1. 什么是双指针

「指针」在这里不是 C 语言里的内存地址，而是一个形象的说法——它就是数组的下标（索引）。双指针就是同时用两个下标变量来遍历数组。

双指针有两种常见模式：

快慢指针：两个指针从同一端出发，速度不同
左右指针：两个指针分别从数组两端出发，向中间靠拢

下面分别来看。

2. 快慢指针

2.1 核心思路

快慢指针就像两个人在跑步——一个跑得快，一个跑得慢。通过观察它们的位置关系，可以发现一些有用的性质。

2.2 经典问题：删除有序数组中的重复项

题目：给定一个升序排列的数组nums，原地删除重复元素，使每个元素只出现一次，返回新数组的长度。

比如输入[1, 1, 2]，处理后数组变成[1, 2, _]，返回 2。

思路：

用一个「慢指针」slow标记当前不重复元素应该存放的位置
用一个「快指针」fast去扫描整个数组
当nums[fast] != nums[slow]时，说明遇到了新的不重复元素，把它放到slow + 1的位置

int removeDuplicates(vector<int>& 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]为例）：

初始: slow=0, fast=1 第 1 轮: nums[1]=1 == nums[0]=1，跳过 → slow=0, fast=2 第 2 轮: nums[2]=2 != nums[0]=1，slow++，赋值 → [1,2,2,2,3], slow=1, fast=3 第 3 轮: nums[3]=2 == nums[1]=2，跳过 → slow=1, fast=4 第 4 轮: nums[4]=3 != nums[1]=2，slow++，赋值 → [1,2,3,2,3], slow=2, fast=5 结束，返回 slow+1 = 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--让和变小

vector<int> twoSum(vector<int>& 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(vector<int>& 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. 双指针的使用场景总结

模式	适用场景	典型题目
快慢指针	检测环、去重、找中点	有序数组去重、链表环检测
左右指针	有序数组上的搜索、求和	两数之和、盛水容器、三数之和

判断是否能用双指针的关键：数据是否有序或者问题是否满足单调性。如果移动一个指针能让结果朝着某个确定方向变化，双指针大概率可行。