算法基础｜双指针核心思想与应用

今天复习双指针技巧，整理一下核心思路和典型用法。双指针是笔试面试中非常高频的算法思想，能把很多问题的时间复杂度从 O (n²) 优化到 O (n)。

目录

一、核心思想

二、典型应用场景

三、例题实战

四、考点提炼

一、核心思想

• 用两个指针分别指向数组 / 链表的不同位置，协同遍历，避免嵌套循环
• 常见形式：对撞指针（左右两端向中间移动）、快慢指针（一快一慢同向移动）
• 「双指针排序」本质是：两个指针分别指向两个有序队列，通过比较移动指针，将符合要求的元素逐步移出，最终完成合并或排序，这也可以看作是快慢指针思想的一种延伸。

二、典型应用场景

1. 数组去重：慢指针记录有效位置，快指针遍历去重
2. 移动零：将非零元素移到前面，零元素移到后面
3. 链表环检测：快慢指针相遇则证明有环
4. 有序数组合并 / 排序：类似归并排序中的合并步骤，用两个指针分别遍历两个有序数组

三、例题实战

解题思路（快慢指针）：

• 慢指针slow：指向当前有效数组的末尾位置（即下一个要保留的元素应该放置的位置）
• 快指针fast：遍历整个数组，检查每个元素
• 因为数组是有序的，所以只需要比较nums[fast]和nums[slow-2]：
  • 如果两者不相等，说明当前元素可以保留，将nums[fast]赋值给nums[slow]，并让slow前进
  • 如果相等，说明当前元素已经出现了两次，需要跳过

代码实现：

class Solution { public int removeDuplicates(int[] nums) { int n = nums.length; if (n <= 2) return n; // 长度<=2时直接返回 int slow = 2; // 慢指针从2开始，保证前两个元素一定保留 for (int fast = 2; fast < n; fast++) { // 快指针元素与慢指针前两个元素不同，说明可以保留 if (nums[fast] != nums[slow - 2]) { nums[slow] = nums[fast]; slow++; } } return slow; } }

思路总结：

• 慢指针 slow 控制有效数组长度，快指针 fast负责遍历检查
• 利用数组有序的特性，通过比较nums[fast]和nums[slow-2]来判断是否重复超过两次
• 时间复杂度 O (n)，空间复杂度 O (1)，完全符合题目要求

四、考点提炼

1. 双指针的核心优势：原地修改数组，避免额外空间开销
2. 有序数组的利用：因为数组有序，重复元素必然连续，所以可以通过比较前两个元素来判断重复次数
3. 边界处理：数组长度 ≤ 2 时直接返回，无需处理