1. 双指针基础知识
1. 双指针简介
双指针(Two Pointers):在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针进行访问,从而达到相应的目的. 如果两个指针方向相反,为对撞指针, 如果指针方向相同,称为快慢指针.如果两个指针分别属于不同的数组/链表,称为分离双指针
时间复杂度从O(n**2)降到了O(n)
2. 对撞指针
- 定义:对撞指针:两个指针left,right分别指向第一个元素和最后一个元素,然后left指针不断递增,right不断递减,直到两个指针相撞或达到其他条件为止
- 步骤:
- 使用两个指针left,right分别指向第一个元素和最后一个元素
- 在循环体中将左右指针相向移动,当满足一定条件时,将左指针右移(+1);当满足一些条件时,将右指针左移(-1)
- 直到两指针相撞或满足其他特殊条件时,跳出循环体
- 适用范围(有序数组或字符串问题):
- 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题
- 字符串反转问题：反转字符串、回文数、颠倒二进制等问题
- 伪代码:
left = 0
right = len(nums) - 1
while left < right:
if 满足要求的特殊条件:
return 符合条件的值
elif 一定条件1:
left += 1
elif 一定条件2:
right -= 1
return 没找到
3. 快慢指针
- 定义:两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为快指针(fast)，移动慢的指针被称为慢指针(slow)。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。
- 步骤:
- 使用两个指针slow和fast.slow一般指向序列的第一个元素(slow = 0), fast一般指向序列的第二个元素(fast = 1)
- 在循环体中将快慢指针向右移动.当满足一定条件时,将慢指针右移(+1), 当满足另一些条件时,将快指针右移(+1)
- 到快指针移动到数组尾端（即 fast == len(nums) - 1），或者两指针相交，或者满足其他特殊条件时跳出循环体
- 适用范围:一般用于处理数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题
- 伪代码:
slow = 0
fast = 1
while 没有遍历完:
if 满足一些条件:
slow += 1
fast += 1
return ans
4. 分离双指针
- 定义:两个指针分别属于不同的数组 / 链表，两个指针分别在两个数组 / 链表中移动。
- 步骤:
- 使用两个指针left_1, left_2.left_1指向第一个数组的第一个元素(left_1 = 0),left_2指向第二个数组的第二个元素(left_2 = 0)
- 当满足一些条件时,两个指针同时右移(left_1 += 1, left_2 += 1)
- 当满足另外一些条件是,left_1右移(left_1 += 1)
- 当满足其它一些条件时,left_2右移(left_2 += 1)
- 当其中一个数组遍历完或一些其他条件时跳出循环
- 适用范围:一般用于处理有序数组合并，求交集、并集问题
- 伪代码:
left_1 = 0
left_2 = 0
while left_1 < len(nums1) and left_2 < len(nums2):
if 一定条件 1:
left_1 += 1
left_2 += 2
elif 一定条件 2:
left_1 += 1
elif 一定条件 3:
left_2 += 1
2. 滑动窗口
2.1 算法介绍
- 滑动窗口（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。
- 操作:
- 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动
- 缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。
- 利用了快慢指针的技巧
2.2 适用范围:
- 一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题
- 种类:
- 固定长度窗口
- 不定长度窗口
- 求解最大的满足条件的窗口
- 求解最小的满足条件的窗口
2.3 固定长度窗口
- 步骤:
假定窗口的固定大小为window_size
- 使用两个指针 left、right。初始时，left 、right 都指向序列的第一个元素，即：left = 0，right = 0 ，区间 [left, right] 被称为一个窗口
- 当窗口未达到 window_size 大小时，不断移动 right，先将 window_size 个元素填入窗口中。
- 当窗口达到 window_size 大小时，判断窗口内的连续元素是否满足题目限定的条件
- 如果满足，再根据要求更新最优解。
- 然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。
- 向右移动 right，将元素填入窗口中
- 重复 2 ~ 4 步，直到 right 到达序列末尾
- 伪代码实现:
left = 0
right = 0
while right < len(nums):
window.append(nums[right])
if right - left + 1 >= window_size:
window.popleft()
left += 1
right += 1
2.4 不定长度窗口
- 步骤:
- 使用两个指针 left、right。初始时，left、right 都指向序列的第一个元素。即：left = 0，right = 0，区间 [left, right] 被称为一个窗口
- 将区间最右侧元素添加入窗口中，即 window.add(s[right])。
- 然后向右移动 right，从而增大窗口长度，即 right += 1。直到窗口中的连续元素满足要求。
- 此时，停止增加窗口大小。转向不断将左侧元素移出窗口，即 window.popleft(s[left])。
- 然后向右移动 left，从而缩小窗口长度，即 left += 1。直到窗口中的连续元素不再满足要求。
- 重复 2 ~ 5 步，直到 right 到达序列末尾。
- 伪代码实现:
left = 0
right = 0
while right < len(nums):
windows.append(nums[right])
while 窗口需要缩小:
window.popleft()
left += 1
right += 1
3. 双指针相关题目:
2.1 对撞指针
- 思路:数组是按照非递减顺序排列,并要我们求两数之和等于target,可以考虑使用对撞指针
- 代码实现:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
elif numbers[left] + numbers[right] > target:
right -= 1
else:
left += 1
- 思路:先将字符串变为小写,再按照ord判断是否是字符串或数字.按照对撞指针的思路来写.
- 代码实现:
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
left = 0
right = len(s) - 1
res_ls = list(range(48, 58)) + list(range(97, 123))
while left < right:
if ord(s[left]) in res_ls and ord(s[right]) in res_ls and s[left] == s[right]:
left += 1
right -= 1
elif ord(s[left]) not in res_ls:
left += 1
elif ord(s[right]) not in res_ls:
right -= 1
else:
return False
return True
- 思路: 按照对撞指针的思路去写,交换left和right位置的字符串.在指针碰撞时跳出循环
- 代码实现:
class Solution:
def reverseString(self, s: List[str]) -> None:
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
- 思路:可以先对数组进行排序,采用三个指针的方式来解决问题:第一个指针为数组中的第一个元素,第三个指针初始值为倒数第一个元素,第二个元素初始值为第一个指针的后一个元素.
第一个指针在for循环内部遍历数组
第二个元素在第一个指针后的元素里面遍历
第三个元素从后往前依次移动
当达到条件时跳出while循环
向最后结果数组中添加结果 - 代码实现:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 对数组进行排序
nums.sort()
n = len(nums)
ans = []
for first in range(n):
# 判断第一个指针选择的数字是否相同
if first >= 1 and nums[first] == nums[first - 1]:
continue
# 第三个指针从最后一个开始
third = n - 1
target = -nums[first]
for second in range(first + 1, n):
# 判断第二个指针是否相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 对撞指针的判断以及指针移动的判断
while second < third and nums[second] + nums[third] > target:
third -= 1
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
2.2 快慢指针
- 定义两个指针slow 和 fast, slow表示以确定的数组位置,fast表示已探索的数组位置,判断fast与slow-2的位置的元素是否相同即可
如果相同,fast + 1
如果不同, 将fast的值赋给slow位置,同时slow和fast加一 - 代码实现:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 0
fast = 0
n = len(nums)
while fast < n:
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
- 思路:快慢指针的思路即可,与上面那道题很相似.定义一个slow和fast指针
当nums[fast] != 0时,交换slow和fast处的数据,同时slow + 1和fast + 1
当nums[fast] == 0时,fast+=1 - 代码实现:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
slow = 0
fast = 0
n = len(nums)
while fast < n:
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
return nums
2.3 分离指针
- 思路: nums1的长度等于两个数组之和,可以联想到从后往前依次覆盖,定义两个分离指针来指代两个数组的最右边,定义一个指针来指代第一个数组中需要排序的最后一个元素
left_1:第一个数组的左边的指针
right_1:第一个数组的右边的指针
right_2:第二个数组的右边的指针
当left_1 = -1时,证明nums1已排序完全,只需要往其覆盖填写nums2即可
当right_2 = -1时,证明nums2已排序完全,只需要往其覆盖填写nums1即可
当right_2 > left_1时,覆盖填写right_2对应元素即可,并更改right_2和right_1
否则,覆盖填写left_1对应元素即可,并更改right_1和left_1 - 代码实现:
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
left_1 = m - 1
right_1 = len(nums1) - 1
right_2 = n - 1
while left_1 >= 0 or right_2 >= 0:
if left_1 == -1:
nums1[right_1] = nums2[right_2]
right_2 -= 1
elif right_2 == -1:
nums1[right_1] = nums1[left_1]
left_1 -= 1
elif nums2[right_2] >= nums1[left_1]:
nums1[right_1] = nums2[right_2]
right_2 -= 1
else:
nums1[right_1] = nums1[left_1]
left_1 -= 1
right_1 -= 1
return nums1
|