双指针算法：高效解题的终极技巧

一、双指针核心思想

双指针：用两个变量模拟指针，在数组 / 链表中同向或反向移动

• 把暴力两层循环 O (n²) 优化为 O (n)
• 无需额外开辟大量空间，空间效率极高
• 刷题最通用、上手最快的算法技巧

两大核心分类：

1. 左右指针（首尾相向移动）
2. 快慢指针（同向一快一慢）

二、类型一：左右指针（相向指针）

适用场景

有序数组、两数之和、反转数组、回文判断、区间收缩

通用模板

int left = 0; int right = nums.size() - 1; while(left < right) { // 逻辑判断 if(满足条件) { left++; } else { right--; } }

例题 1：反转数组

void reverseArray(vector<int>& nums) { int l = 0, r = nums.size()-1; while(l < r) { swap(nums[l],nums[r]); l++; r--; } }

例题 2：判断回文字符串

bool isPalindrome(string s) { int l = 0, r = s.size()-1; while(l < r) { if(s[l] != s[r]) return false; l++; r--; } return true; }

例题 3：有序数组两数之和

vector<int> twoSum(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l < r) { int sum = nums[l] + nums[r]; if(sum == target) return {l+1, r+1}; else if(sum < target) l++; else r--; } return {}; }

三、类型二：快慢指针（同向指针）

适用场景

链表找中点、链表判环、数组去重、移动零、删除元素

通用模板

int slow = 0; int fast = 0; while(fast < nums.size()) { // 快指针先行 if(满足条件) { nums[slow++] = nums[fast]; } fast++; }

例题 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; }

例题 2：移动零到数组末尾

void moveZeroes(vector<int>& nums) { int slow = 0; for(int fast = 0; fast < nums.size(); fast++) { if(nums[fast] != 0) { swap(nums[slow],nums[fast]); slow++; } } }

链表快慢指针经典用法

1. 快指针走两步，慢指针走一步 →找链表中间节点
2. 快慢指针相遇 →判断链表是否有环

四、双指针选型口诀

1. 数组有序、首尾查找、对称判断 →左右指针
2. 数组去重、元素筛选、链表操作 →快慢指针
3. 无序数组优先哈希，有序数组优先双指针

五、双指针高频刷题题型汇总

1. 数组反转、字符串反转
2. 回文串校验
3. 有序数组两数 / 三数之和
4. 原地删除元素
5. 数组移动零
6. 链表找中点、链表判环
7. 盛最多水容器

六、新手易错点

1. 左右指针循环条件写成left<=right造成重复处理
2. 快慢指针快慢移动顺序写反
3. 无序数组强行使用左右指针导致逻辑错误
4. 原地修改数组后忘记更新有效长度

七、今日总结

1. 双指针核心：一左一右 / 一快一慢
2. 左右指针相向而行，解决有序区间问题
3. 快慢指针同向而行，完成元素筛选与原地操作
4. 绝大多数数组简单算法题，优先考虑双指针优化