数组双指针技巧总结
raw/articles/2026/05/数组双指针技巧总结
一句话总结
系统讲解数组中的双指针技巧，分为快慢指针（原地修改、滑动窗口）和左右指针（二分查找、n数之和、反转、回文）两大类，配合 LeetCode 经典题目实践。
核心要点
1. 双指针两大分类
数组中的双指针技巧主要分为两类：
| 类型 | 指针移动方式 | 典型应用 |
|---|---|---|
| 快慢指针 | 同向而行，一快一慢 | 原地修改、滑动窗口 |
| 左右指针 | 相向而行或相背而行 | 二分查找、n数之和、反转、回文 |
2. 快慢指针：原地修改
核心思想：慢指针 slow 走在后面，快指针 fast 走在前面探路，找到符合条件的元素就赋值给 slow 并前进。
经典问题：
| LeetCode | 问题 | 核心逻辑 |
|---|---|---|
| 26 | 删除有序数组中的重复项 | fast 找到不重复元素→赋值给 nums[slow]→slow++ |
| 27 | 移除元素 | fast 遇到非 val 元素→赋值给 nums[slow]→slow++ |
| 283 | 移动零 | 复用 #27 思路移除0，再将后半部分置0 |
通用模板：
int slow = 0, fast = 0;
while (fast < nums.length) {
if (符合条件) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow; // 新长度
3. 快慢指针：滑动窗口
快慢指针形成窗口，通过扩大/缩小窗口解决问题。
通用框架：
int left = 0, right = 0;
while (right < nums.size()) {
window.addLast(nums[right]);
right++;
while (window needs shrink) {
window.removeFirst(nums[left]);
left++;
}
}
4. 左右指针：相向移动
二分查找：
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
两数之和 II（有序数组）：
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{left + 1, right + 1};
else if (sum < target) left++;
else right--;
}
5. 左右指针：从中心扩散
反转数组/字符串：
int left = 0, right = s.length - 1;
while (left < right) {
swap(s[left], s[right]);
left++; right--;
}
回文串判断：
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++; right--;
}
return true;
最长回文子串：
for (int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i); // 奇数长度
String s2 = palindrome(s, i, i + 1); // 偶数长度
res = longer(res, s1, s2);
}
基本原理
快慢指针原理
初始： [1, 1, 2, 2, 3]
↑ ↑
slow fast
处理： fast 找到不同元素 → 赋值给 slow → slow 前进
结果： [1, 2, 3, 2, 3]
↑
slow (新长度=3)
左右指针原理
两数之和：
初始： [2, 7, 11, 15], target=9
↑ ↑
left right
sum=17 > 9, right--
调整： [2, 7, 11, 15]
↑ ↑
left right
sum=9 == 9, 返回 [1, 2]
时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 原地修改（去重/移除） | O(N) | 一次遍历，fast 指针扫描全部 |
| 滑动窗口 | O(N) | 均摊分析，每个元素进出窗口各一次 |
| 二分查找 | O(log N) | 每次缩小一半搜索范围 |
| 两数之和（有序） | O(N) | 最坏情况左右指针遍历整个数组 |
| 反转数组 | O(N) | 交换 n/2 次 |
| 最长回文子串 | O(N²) | 每个中心扩展，最坏情况 O(N²) |
代码实现
关键代码片段
#26 删除有序数组中的重复项：
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
}
#27 移除元素：
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
#283 移动零（复用 #27）：
class Solution {
public void moveZeroes(int[] nums) {
int p = removeElement(nums, 0);
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
#167 两数之和 II：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
}
#5 最长回文子串：
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i); // 奇数长度
String s2 = palindrome(s, i, i + 1); // 偶数长度
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length()
&& s.charAt(l) == s.charAt(r)) {
l--; r++;
}
return s.substring(l + 1, r);
}
}
实现要点
- 快慢指针：
slow记录有效位置，fast探路；先判断再赋值（或先赋值再判断，取决于问题） - 左右指针相向：根据条件移动
left或right，注意循环条件left < right - 回文中心扩散：考虑奇数/偶数两种中心情况；
while循环后返回[l+1, r)
对比分析
| 维度 | 快慢指针 | 左右指针 |
|---|---|---|
| 指针方向 | 同向 | 相向或中心扩散 |
| 典型应用 | 原地修改、滑动窗口 | 二分、n数之和、反转、回文 |
| 时间复杂度 | O(N) | O(N) 或 O(log N) |
| 空间复杂度 | O(1) | O(1) |
| 适用结构 | 数组、链表 | 数组、字符串 |
| 维度 | 对向指针（左右） | 中心扩散（左右） |
|---|---|---|
| 指针起点 | 两端 | 中心 |
| 移动方向 | 向中间 | 向两端 |
| 典型问题 | 二分、两数之和 | 回文串 |
应用场景
- 原地修改数组：去重、删除特定元素、移动零
- 滑动窗口：最小覆盖子串、无重复字符最长子串、和≥target的最短子数组
- 有序数组查找：二分查找、两数之和
- 字符串处理：反转、回文判断、最长回文子串
验证方法
可通过以下 LeetCode 题目验证：
| 平台 | 题目 | 难度 | 对应技巧 |
|---|---|---|---|
| LeetCode | #26 删除有序数组中的重复项 | Easy | 快慢指针-原地修改 |
| LeetCode | #83 删除排序链表中的重复元素 | Easy | 快慢指针（链表版） |
| LeetCode | #27 移除元素 | Easy | 快慢指针-原地修改 |
| LeetCode | #283 移动零 | Easy | 快慢指针-原地修改 |
| LeetCode | #167 两数之和 II | Medium | 左右指针-对向 |
| LeetCode | #344 反转字符串 | Easy | 左右指针-对向 |
| LeetCode | #5 最长回文子串 | Medium | 左右指针-中心扩散 |
相关概念
相关实体
- labuladong：本文作者，算法学习平台
- LeetCode：本文涉及的题目来源平台
总结
数组双指针技巧通过将嵌套循环优化为线性扫描，将时间复杂度从 O(N²) 降低到 O(N)。快慢指针适用于原地修改和滑动窗口场景，左右指针适用于二分查找、n数之和、反转和回文问题。掌握这两大类技巧，可以解决大部分数组相关的算法问题。