双指针算法从原理到实战搞定数组/字符串高频题在算法世界中双指针是一种简单却极具威力的优化思想。它通过两个指针的协同移动将暴力解法的O(n2)O(n^2)O(n2)时间复杂度优化到O(n)O(n)O(n)尤其适用于数组、字符串、链表等线性数据结构的问题。本文将基于「比特就业课」优选算法精品课的双指针内容从核心原理、常见类型到经典实战例题带你彻底吃透双指针算法。一、双指针算法核心原理双指针的核心思想是用两个指针遍历数据结构通过指针的移动规则减少不必要的遍历。不同于暴力解法的嵌套循环双指针仅需一次或两次线性遍历即可完成任务本质是利用数据的有序性、连续性等特性缩小查找或处理的范围。双指针的关键在于确定指针的初始位置如数组两端、起始位置定义指针的移动规则如向中间靠拢、一快一慢、同向移动明确算法的终止条件如指针相遇、指针越界。二、双指针的三大常见类型根据指针的移动方式双指针主要分为「对撞指针」「快慢指针」和「数组划分指针」三类每类都有其典型应用场景。1. 对撞指针左右指针核心特点指针起始位置数组/字符串的两端left0rightn-1移动方向向中间靠拢终止条件left right指针相遇或 left right指针错开适用场景有序数组/字符串的查找、区间最值、两数/三数之和等问题。核心原理对撞指针利用数据的有序性或特定分布特性每次移动一个指针就能排除一部分无效区间。例如在有序数组中通过比较左右指针指向元素的和与目标值的大小可快速缩小查找范围。2. 快慢指针龟兔赛跑算法核心特点指针起始位置通常都在数组/链表的起始位置slow0fast0移动方向同向移动但速度不同如慢指针走1步快指针走2步终止条件快指针到达数据末尾、快慢指针相遇检测循环适用场景环形结构检测、链表中点查找、数组中重复元素处理、快乐数等存在循环的问题。核心原理快慢指针的核心是利用「速度差」制造距离。例如在环形链表中快指针最终会追上慢指针在数组去重中快指针负责遍历元素慢指针负责标记有效位置。3. 数组划分指针核心特点指针起始位置一个指针cur从起始位置遍历另一个指针dest标记目标区间边界如非零元素末尾移动方向同向移动cur 负责遍历dest 负责定位终止条件cur 遍历完整个数组适用场景数组按条件划分如移动零、复写零、元素分类等问题。核心原理通过两个指针划分数组区间例如将数组分为「非零元素区」和「零元素区」cur 遍历过程中不断扩大目标区间dest 始终指向目标区间的末尾。三、经典实战例题从基础到进阶下面结合 LeetCode 高频题详解各类双指针的应用的每道题均附核心思路和代码实现。例题1移动零Easy数组划分指针题目链接283. 移动零题目描述给定一个数组nums将所有 0 移动到数组末尾保持非零元素的相对顺序要求原地操作。示例输入nums [0,1,0,3,12]输出[1,3,12,0,0]核心思路利用「数组划分」思想用两个指针划分区间cur遍历整个数组寻找非零元素dest标记非零元素区间的最后一个位置初始为 -1表示暂无非零元素规则当nums[cur] ! 0时dest先向后移动一位扩大非零区间再交换nums[cur]和nums[dest]当nums[cur] 0时cur直接向后移动零元素自动归入另一区间最终效果[0, dest]为非零元素区间[dest1, cur-1]为零元素区间。Java 代码实现class Solution { public void moveZeroes(int[] nums) { for(int cur 0, dest -1; cur nums.length; cur) { if(nums[cur] ! 0) { // 仅处理非零元素 dest; // 非零区间扩大一位 // 交换cur和dest位置的元素 int tmp nums[cur]; nums[cur] nums[dest]; nums[dest] tmp; } } } }性能表现时间复杂度O(n)O(n)O(n)仅一次遍历空间复杂度O(1)O(1)O(1)原地操作执行结果Java 代码耗时 1ms击败 100% 提交。例题2盛最多水的容器Medium对撞指针题目链接11. 盛最多水的容器题目描述给定一个整数数组height表示 n 条垂线的高度找出两条垂线使其与 x 轴构成的容器能容纳最多的水不能倾斜容器。示例输入height [1,8,6,2,5,4,8,3,7]输出49核心思路容器的容积由「短板高度」和「指针间距」决定容积 指针间距 * min(左板高度, 右板高度)。利用对撞指针优化初始位置left0左端点rightheight.length-1右端点移动规则若height[left] height[right]左板是短板移动左指针left因为移动右指针只会让容积变小间距减小短板不变否则右板是短板移动右指针right--终止条件left right遍历过程中记录最大容积。Java 代码实现class Solution { public int maxArea(int[] height) { int left 0, right height.length - 1, maxVol 0; while(left right) { // 计算当前容积 int vol Math.min(height[left], height[right]) * (right - left); maxVol Math.max(maxVol, vol); // 移动短板指针 if(height[left] height[right]) left; else right--; } return maxVol; } }性能表现时间复杂度O(n)O(n)O(n)一次遍历空间复杂度O(1)O(1)O(1)执行结果Java 代码耗时 4ms击败 60.7% 提交。例题3快乐数Medium快慢指针题目链接202. 快乐数题目描述「快乐数」定义对于正整数 n每次将其替换为每个位置上数字的平方和重复该过程若最终能得到 1 则为快乐数若无限循环则不是。示例输入n19输出true19→82→68→100→1核心思路快乐数的关键是判断「是否存在循环」若存在循环且循环节点不是 1则不是快乐数利用快慢指针检测循环慢指针slow每次执行 1 次平方和操作快指针fast每次执行 2 次平方和操作终止条件快慢指针相遇若相遇时的值为 1则是快乐数否则不是快指针先到达 1直接返回 true。辅助函数计算数字的平方和private int bitSum(int n) { int sum 0; while(n ! 0) { int t n % 10; // 提取个位 sum t * t; n / 10; // 移除个位 } return sum; }Java 代码实现class Solution { public boolean isHappy(int n) { int slow n, fast bitSum(n); while(slow ! fast) { slow bitSum(slow); // 慢指针走1步 fast bitSum(bitSum(fast)); // 快指针走2步 } return slow 1; // 相遇时是否为1 } private int bitSum(int n) { int sum 0; while(n ! 0) { int t n % 10; sum t * t; n / 10; } return sum; } }性能表现时间复杂度O(logn)O(log n)O(logn)每次平方和操作会减少数字位数空间复杂度O(1)O(1)O(1)执行结果Java 代码耗时 0ms击败 100% 提交。例题4三数之和Medium对撞指针排序题目链接15. 三数之和题目描述给你一个整数数组nums找出所有和为 0 且不重复的三元组i≠j≠k。示例输入nums [-1,0,1,2,-1,-4]输出[[-1,-1,2],[-1,0,1]]核心思路三数之和可转化为「固定一个数 两数之和」利用排序对撞指针优化排序先对数组排序便于去重和双指针查找固定数a遍历数组固定nums[i]为a目标转化为在i1到n-1区间找两个数使其和为-a对撞指针lefti1rightn-1查找两数之和去重固定数a去重若nums[i] nums[i-1]跳过避免重复三元组双指针去重找到有效三元组后left和right分别跳过重复元素。Java 代码实现import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger result new ArrayList(); Arrays.sort(nums); // 排序 int n nums.length; for(int i 0; i n; ) { if(nums[i] 0) break; // 优化a0时三数和不可能为0 int target -nums[i]; int left i 1, right n - 1; while(left right) { int sum nums[left] nums[right]; if(sum target) { right--; } else if(sum target) { left; } else { // 找到有效三元组 result.add(new ArrayList(Arrays.asList(nums[i], nums[left], nums[right]))); left; right--; // 双指针去重 while(left right nums[left] nums[left-1]) left; while(left right nums[right] nums[right1]) right--; } } // 固定数a去重 i; while(i n nums[i] nums[i-1]) i; } return result; } }性能表现时间复杂度O(n2)O(n^2)O(n2)排序O(nlogn)O(n log n)O(nlogn) 遍历双指针O(n2)O(n^2)O(n2)空间复杂度O(logn)O(log n)O(logn)排序所需空间执行结果Java 代码耗时 26ms击败 98.56% 提交。四、双指针算法解题技巧总结先判断数据特性有序数组优先考虑对撞指针环形问题优先快慢指针数组划分问题用同向双指针注重边界处理避免指针越界如right nums.length - 1、重复元素去重三数之和、两数之和学会问题转化将三数之和转化为两数之和将快乐数循环检测转化为快慢指针相遇问题原地操作优先双指针算法的核心优势之一是原地操作减少额外空间开销如移动零、复写零多练习找规律双指针的移动规则虽灵活但同类题目有固定套路多做例题就能快速上手。五、总结双指针算法是优化线性数据结构问题的“利器”其核心是通过指针的协同移动减少无效遍历。无论是简单的移动零、盛最多水的容器还是中等难度的快乐数、三数之和掌握双指针的三类核心类型和解题技巧就能高效解决这类高频题。建议大家结合本文的例题反复练习重点体会“指针移动规则”的设计思路再尝试独立解决同类题目如四数之和、有效三角形的个数相信你能快速掌握双指针算法的精髓如果需要进一步巩固可以尝试用双指针解决「复写零」「和为s的两个数字」等题目检验自己的学习成果~