4.1 双指针解释

<aside> 🪬

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

</aside>

在数组的区间问题上，暴力算法的时间复杂度往往是 O(n2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

4.2 对撞指针

<aside> 🪬

对撞指针：指的是两个指针 left、right分别指向序列第一个元素和最后一个元素，然后left 指针不断递增，right不断递减，直到两个指针的值相撞，或者满足其他要求的特殊条件为止。

</aside>

4.3 伪代码模版

<aside> 🪬

left, right = 0, len(nums) - 1

while left < right: if 满足要求的特殊条件: return 符合条件的值 elif 一定条件 1: left += 1 elif 一定条件 2: right -= 1

return 没找到 或 找到对应值

</aside>

4.4 啥时候用

对撞指针一般用来解决有序数组或者字符串问题：

• 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
• 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

例题：两数之和

描述：给定一个下标从 11 开始计数、升序排列的整数数组：numbers 和一个目标值 target。

要求：从数组中找出满足相加之和等于 target 的两个数，并返回两个数在数组中下的标值。

示例：

<aside> 🪬

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

</aside>