目录：
算法5 — 双指针（python）
🍄 `基本思想：
双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞时针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。
🍁 核心思想：
双指针算法最核心的用途就是优化时间复杂度。
- 原本两个指针是有 [公式] 种组合，因此时间复杂度是 O ( n 2 ) O(n^2) O(n2) 。
- 而双指针算法就是运用单调性使得指针只能单向移动，因此总的时间复杂度只有 O ( 2 n ) O(2n) O(2n)，也就是 O ( n ) O(n) O(n)。
- 之所以双指针可以实现 O ( n ) O(n) O(n)的时间复杂度是因为指针只能单向移动，
没有指针的回溯，而且每一步都会有指针移动。- 而朴素的 O ( n 2 ) O(n^2) O(n2)算法的问题就在于指针经常
回溯到之前的位置。
基本方法：
while j < i:
// 每道题目的具体逻辑
j += 1
i += 1
}
- 因为双指针算法是一种优化时间复杂度的方法，所以我们可以首先写出最朴素的两层循环的写法。
- 然后考虑题目中是否具有单调性。
- 即当其中一个指针 i i i 向后移动时，在希望得到答案的情况下，另一个指针 j j j
是不是只能向着一个方向移动。- 如果
是，说明题目具有单调性，可以通过双指针算法优化。
🍄 对撞指针
对撞指针：指的是两个指针 left、right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增，right 不断递减，直到两个指针的值相撞（即 left == right），或者满足其他要求的特殊条件为止。
🍁 对撞指针求解步骤
- 使用两个指针 left，right。left 指向序列第一个元素，即：left = 0，right 指向序列最后一个元素，即：right = len(nums) - 1。
- 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left += 1。当满足另外一定条件时，将右指针左移，right -= 1。
- 直到两指针相撞（即 left == right），或者满足其他要求的特殊条件时，跳出循环体。
🐾 对撞指针伪代码模板
left = 0
right = len(nums) - 1
while left < right:
if 满足要求的特殊条件:
return 符合条件的值
elif 一定条件 1:
left += 1
elif 一定条件 2:
right -= 1
return 没找到 或 对应值
?? 对撞指针适用范围
-
对撞指针一般用来解决有序数组或者字符串问题：
-
查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
-
字符串反转问题：反转字符串、回文数、颠倒二进制等问题。
下面我们根据具体例子来讲解如何使用对撞指针来解决问题。
🚩 例子应用1??：
题目描述—167. 两数之和 II - 输入有序数组
- 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
- 如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
- 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
- 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
- 你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
💡 提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
代码如下：
class Solution:
def twoSum(self, numbers: list, target: int) -> list:
left, right = 0, len(numbers) - 1
"""开始遍历"""
while left <= right:
sum_ = numbers[left] + numbers[right]
"""如果比目标值小，则左端向后移动一位，让 sum_ 大一点"""
if sum_ < target:
left += 1
elif sum_ > target:
"""如果比目标值大，则右端向前移动一位，让 sum_ 小一点"""
right -= 1
else:
"""与目标值相等，由于数组下标是从1开始，故左右端都+1"""
return [left + 1, right + 1]
if __name__ == "__main__":
S = Solution()
numbers = [2,7,11,15]; target = 9
res = S.twoSum(numbers,target)
print(res)
numbers2 = [2, 3, 4]; target2 = 6
res2 = S.twoSum(numbers2, target2)
print(res2)
[1, 2]
[1, 3]
🚩 例子应用2??：
- 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
💡 提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
注： 两个数组是要进行排序的
代码如下：
class Solution:
def intersection(self, nums1: list, nums2: list) -> list:
# 分离双指针一般用于处理有序数组合并，求交集、并集问题
# 1 先将两个数组排序
nums1.sort()
nums2.sort()
# 使用双指针求交集
Result = []
point1 = 0
point2 = 0
while point1 < len(nums1) and point2 <len(nums2):
# 元素同时出现在两个数组
if nums1[point1] == nums2[point2]:
# 保证数组没有重复元素
if nums1[point1] not in Result:
Result.append(nums1[point1])
point1 += 1
point2 += 1
# point1落后于point2，需要追赶
elif nums1[point1] < nums2[point2]:
point1 += 1
# point2落后于point1，需要追赶
elif nums1[point1] > nums2[point2]:
point2 += 1
return Result
if __name__ == "__main__":
S = Solution()
"""## 示例2"""
# nums1 = [1,2,2,1]
# nums2 = [2,2]
# result = S.intersection(nums1,nums2)
# print("结果：",result)
"""## 示例2"""
nums1 = [4, 9, 5]; nums2 = [9, 4, 9, 8, 4]
result = S.intersection(nums1, nums2)
print("结果：", result)
结果： [4, 9]
💕 这些只是本人用来记录学习算法内容的一些笔记，用来监督自己学习的，有不对的地方望指正！
?
?
?
【参考文献】
参考来源：https://algo.itcharge.cn/
