Python算法——双指针

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。

双指针分为「对撞指针」、「快慢指针」、「分离双指针」。

    对撞指针：两个指针方向相反。适合解决查找有序数组中满足某些约束条件的一组元素问题、字符串反转问题。

    快慢指针：两个指针方向相同。适合解决数组中的移动、删除元素问题，或者链表中的判断是否有环、长度问题。

    分离双指针：两个指针分别属于不同的数组 / 链表。适合解决有序数组合并，求交集、并集问题。

一，对撞指针

1.盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组
[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

class Solution:def maxArea(self, height: List[int]) -> int:result = 0left = 0right = len(height) - 1while left < right:# 求解矩形的面积l = right - lefth = min(height[left], height[right])area = l*h# 需要不断维持更新最大值result = max(result, area)# 应该使得 较低直线的高度尽可能的高# 当left指向的直线高度较低，向右移动if height[left] < height[right]:left += 1# 当right指向的直线高度较低，向左移动else:right -= 1return result

2.反转字符串

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""left = 0right = len(s) - 1while left < right:s[left], s[right] = s[right], s[left]left += 1right -= 1return s

二，快慢指针

删除有序数组中的重复项

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素

class Solution:def removeDuplicates(self, nums: List[int]) -> int:# 定义两个指针slow = 0fast = 1# 可以视作把非重复元素放在数组左边while fast < len(nums):if nums[slow] != nums[fast]:slow += 1nums[slow] = nums[fast]fast += 1return slow + 1

三，分离指针

两个数组的交集

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:# 分离双指针一般用于处理有序数组合并，求交集、并集问题# 1 先将两个数组排序nums1.sort()nums2.sort()# 使用双指针求交集point1 = 0point2 = 0result = []while point1 < len(nums1) and point2 < len(nums2):# 元素同时出现在两个数组if nums1[point1] == nums2[point2]:# 保证数组没有重复元素if nums1[point1] not in result:result.append(nums1[point1])# 齐头并进point1 += 1point2 += 1# point1落后于point2，需要追赶elif nums1[point1] < nums2[point2]:point1 += 1# point2落后于point1，需要追赶   else:point2 += 1return result

其他类型

合并两个有序数组

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

        # 定义两个指针，分别指向数组的尾部p1 = m-1p2 = n-1p = m + n - 1while p1 >= 0 and p2 >= 0:if nums1[p1] <= nums2[p2]:nums1[p] = nums2[p2]p2 -= 1else:nums1[p] = nums1[p1]p1 -= 1p -= 1# 最后把nums2中的剩余元素赋值到nums1中nums1[:p2+1] = nums2[:p2+1]

删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = 2fast = 2# 因为有序，所以当 nums[slow-2] = nums[slow]时，# 必有nums[slow] = nums[slow-1] = nums[slow-2]# 不相等时进行添加while fast < len(nums):if nums[slow-2] != nums[fast]:nums[slow] = nums[fast]slow += 1fast += 1return slow

三位数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:result = []                  # 结果输出n = len(nums)# 先将数组递增排列nums.sort()# 定义双指针 a, left, rightfor i in range(n):if i > 0 and nums[i] == nums[i-1]:continueleft = i+1right = n-1# 双指针寻找区间while left < right:# 答案中不可以包含重复的三元组，对于重复的元素直接跳过while left < right and left > i+1 and nums[left] == nums[left-1]:left += 1while left < right and right < n-1 and nums[right] == nums[right+1]:right -= 1# 满足条件的三元组if left < right and nums[i] + nums[left] + nums[right] == 0:result.append([nums[i], nums[left], nums[right]])left += 1right -= 1elif nums[i] + nums[left] + nums[right] > 0:right -= 1else:left += 1return result

以上问题都来源于力扣：

力扣>
参考来源：https://algo.itcharge.cn/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！