PHP双指针算法需按问题类型选模式:左右指针用于有序查找与对撞,快慢指针用于原地去重与环检测,同向指针(滑动窗口)用于动态区间问题,反向归并与哈希计数法分别适配原地合并与最小覆盖子串。

PHP中实现双指针算法技巧,需依据问题类型选择对应指针模式:左右指针适用于有序结构查找与对撞操作,快慢指针适用于原地去重与环检测,同向指针(滑动窗口)适用于子数组/子串动态区间问题。以下是多种可直接落地的实现方法:
一、左右指针法:解决有序数组两数之和
该方法利用数组升序特性,通过头尾指针相向移动缩小搜索空间,避免嵌套循环,时间复杂度为O(n)。初始化左指针指向首元素、右指针指向末元素,根据当前和与目标值的大小关系决定移动方向。
1、对输入数组进行升序排序(若未排序);
2、初始化 $left = 0,$right = count($nums) - 1;
3、进入 while ($left
4、计算 $sum = $nums[$left] + $nums[$right];
5、若 $sum == $target,返回 [$left + 1, $right + 1](下标从1开始);
6、若 $sum
7、若 $sum > $target,执行 $right--。
二、快慢指针法:原地删除有序数组重复项
利用数组已排序的前提,慢指针标记已确认唯一元素的边界,快指针扫描新候选值;仅当快指针遇到不同于慢指针位置的值时,慢指针才前移并赋值,从而实现O(1)空间原地去重。
1、若数组长度小于2,直接返回 count($nums);
2、设置 $i = 0(慢指针),$j = 1(快指针);
3、遍历至 $j
4、若 $nums[$j] != $nums[$i],则 $i++ 并 $nums[$i] = $nums[$j];
5、每次循环后 $j++;
6、遍历结束后返回 $i + 1 作为新长度。
三、同向指针法(滑动窗口):求最长无重复字符子串长度
通过维护动态窗口 [left, right],用关联数组记录字符最新出现索引,右指针扩展时遇重复则将左指针跳至该字符上次出现位置+1,确保窗口内无重复,时间复杂度O(n)。
1、初始化 $left = 0,$maxLen = 0,$seen = [](空数组);
2、使用 $right 遍历字符串 $s 的每个字符及其索引;
3、若 isset($seen[$s[$right]]) 且 $seen[$s[$right]] >= $left,则 $left = $seen[$s[$right]] + 1;
4、更新 $seen[$s[$right]] = $right;
5、计算当前窗口长度 $right - $left + 1,并更新 $maxLen;
6、遍历完成后返回 $maxLen。
四、反向归并指针法:原地合并两个有序数组(LeetCode 88)
当第一个数组尾部预留足够空间时,从后往前归并可避免覆盖未处理元素。使用三指针:i 指向 nums1 有效末尾,j 指向 nums2 末尾,k 指向合并后数组末尾,逐次取较大值填入 k 位。
1、设 $i = $m - 1,$j = $n - 1,$k = $m + $n - 1;
2、while ($i >= 0 && $j >= 0) 中比较 $nums1[$i] 与 $nums2[$j];
3、若 $nums1[$i] >= $nums2[$j],则 $nums1[$k--] = $nums1[$i--];
4、否则 $nums1[$k--] = $nums2[$j--];
5、若 $j >= 0,循环执行 $nums1[$k--] = $nums2[$j--];
6、$i 剩余部分无需操作(已在正确位置)。
五、双指针+哈希计数法:最小覆盖子串(s 包含 t 所有字符的最短子串)
维护滑动窗口内各字符频次,用 $need 数组统计 t 中各字符需求量,$window 记录当前窗口频次,$valid 表示已满足需求的字符种类数;仅当 $valid 等于 $need 键数量时尝试收缩左边界。
1、构建 $need = [],遍历 $t 统计每字符出现次数;
2、初始化 $left = $right = 0,$valid = 0,$window = [];
3、while ($right
4、若 isset($need[$c]),则 $window[$c]++,且当 $window[$c] == $need[$c] 时 $valid++;
5、while ($valid == count($need)) 尝试收缩:更新最短子串起始与长度,获取左字符 $d = $s[$left];
6、若 isset($need[$d]),则 $window[$d]--,且当 $window[$d]
7、$left++ 后继续收缩判断。
php免费学习视频:立即使用
踏上前端学习之旅,开启通往精通之路!从前端基础到项目实战,循序渐进,一步一个脚印,迈向巅峰!











