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

数组算法-双指针

news 2026/5/12 20:48:07

首先，双指针法，本质是通过两个索引（指针）在数组上移动，用一次遍历（O (n) 时间复杂度）替代嵌套循环（O (n²)），核心是用空间换时间（仅额外使用两个变量，空间复杂度 O (1)）。

指针的移动规则根据问题场景而定，但核心都是：通过指针的协作，缩小处理范围，避免重复计算。

1.左右指针（左 = 0，右 = len-1，向中间相遇）

1.适用：数组有序或问题具有对称性，无需遍历所有元素，通过两端收缩即可找到解。

数组 / 字符串的对称操作：反转数组、反转字符串、判断回文数 / 回文字符串
有序数组的两数之和：找两个数和为目标值（LeetCode LCR 006，167）
有序数组的区间收缩：最接近目标值的两数之和、两数之差等于目标值

2.循环条件：left < right（无需<=，相遇即终止）

3.移动规则：根据条件单向移动（左指针右移增大值，右指针左移减小值）

例 1：

我们分析题目信息发现“数组有序”“要找两数之和为目标数”，那么就可以使用左右指针解答：

intleft=0,right=numbers.length-1;while(left<right){if(numbers[left]+numbers[right]>target){right--;}elseif(numbers[left]+numbers[right]<target){left++;}else{break;}}returnnewint[]{left,right};

最后我们还要注意边界校验，此题告诉我们一定存在结果，追求简洁可不加；但通常我们还要加上：

if (numbers == null || numbers.length < 2) return new int[]{-1, -1};表示无结果

2.快慢指针（慢指针定有效边界，快指针遍历全数组，同向移动）

1.适用：需要原地修改数组，需筛选 / 保留有效元素，剔除无效元素（重复、指定值、0 值等）。

有序数组去重（LeetCode 26）
移除数组中指定值的元素（LeetCode 27）
移动数组中的 0 到末尾（保留非 0 元素的相对顺序）
筛选数组中的有效元素（如只保留偶数、只保留正数）

2.循环条件：fast < nums.length（快指针遍历完数组即终止）

3.移动规则：快指针找到有效元素时，慢指针先右移（扩大有效区域）再赋值覆盖，否则快指针单独右移

4.结果返回：slow + 1（慢指针是索引，有效数组长度 = 索引 + 1）

例 2：

我们看题干中出现”非严格递增排列“，”原地删除“和”只出现一次“的字样，确定此题属于有序数组去重，可以使用快慢指针解题：

intslow=0;for(intfast=1;fast<nums.length;fast++){if(nums[slow]!=nums[fast]){slow++;nums[slow]=nums[fast];}}returnslow+1;

例 3：

先分析题干“原地”，“移除指定值”，可以使用快慢指针解题：

intslow=0;for(intfast=0;fast<nums.length;fast++){if(nums[fast]!=val){nums[slow]=nums[fast];slow++;}}returnslow;

3. 滑动窗口（动态快慢指针，形成可变窗口，同向移动）

1.适用：子串的最值（最长 / 最短）、满足条件的子数组（和≥目标值、和为 k、无重复元素），问题聚焦连续区间的筛选。

长度最小的子数组（和≥目标值，LeetCode209）
最长无重复元素的子数组
固定长度子数组的最大和 / 最小和
子数组的和等于 k 的最短长度

2.循环条件：fast < nums.length（右指针遍历完数组即终止）

3.左指针：窗口左边界（控制窗口收缩）

4.右指针：窗口右边界（控制窗口扩大）

5.核心逻辑：右指针扩大窗口找解，左指针收缩窗口优化解

例 4：

求子数组，这是一个带条件（sum>=target) 的连续区间，即可以使用滑动窗口解题：

if(nums.length==0||nums==null)return0;intsum=0;intminLen=Integer.MAX_VALUE;intleft=0;for(intright=0;right<nums.length;right++){sum+=nums[right];while(sum>=target){minLen=Math.min(minLen,right-left+1);sum-=nums[left];left++;}}returnminLen==Integer.MAX_VALUE?0:minLen;