Python双指针算法模板和题目同向相向快速排序归并排序

双指针算法是一种在数组或列表中通过两个指针（通常称为左指针和右指针）协同工作来解决问题的高效方法。它广泛应用于各种算法题中，包括但不限于排序、查找、去重等任务。本篇文章将深入探讨Python中的双指针算法，包括同向双指针和相向双指针的模板及其应用。 ### 同向双指针 同向双指针通常从数组的一端开始，两个指针以相同的速度或不同速度向同一方向移动。以下是一些使用同向双指针的典型问题： 1. **数组去重问题**：通过排序数组，然后用一个快指针和一个慢指针，当快指针找到与慢指针不同的元素时，将该元素移到慢指针的位置，从而实现原地去重。 ```python class Solution: def deduplication(self, nums): n = len(nums) if n == 0: return 0 nums.sort() slow = fast = 0 while fast < n - 1: if nums[fast] != nums[fast + 1]: nums[slow + 1] = nums[fast + 1] slow += 1 fast += 1 return slow + 1 ``` 2. **滑动窗口问题**：寻找数组中满足特定条件的子数组。例如，求数组中连续k个数字的和小于等于某个阈值的最大长度。 3. **两数之差问题**：找出数组中两数之差为给定值的组合。 4. **链表中点问题**：找到链表的中间节点，通过两个指针，一个每次移动一步，另一个每次移动两步，当快指针到达链表尾部时，慢指针位于中间。 5. **带环链表问题**：检测链表是否存在环，快慢指针用于判断是否存在环，如果存在，它们将在环内相遇。 ### 相向双指针 相向双指针从数组的两端开始，分别向中间移动，直至相遇或交叉。常见的应用场景包括： 1. **两数之和**：经典的双指针问题，给定一个数组和目标值，找到数组中两个数，使其和为目标值。通过排序数组，使用相向双指针，可以高效地找到答案。 ```python class Solution: def twoSum(self, numbers, target): numbers.sort() L, R = 0, len(numbers) - 1 while L < R: if numbers[L] + numbers[R] == target: return (numbers[L], numbers[R]) if numbers[L] + numbers[R] < target: L += 1 else: R -= 1 return None ``` 2. **回文串判断**：给定一个字符串，检查是否为回文串。通过设置两个指针，一个从字符串开头，一个从结尾开始，逐字符比较。 ```python def isPalindrome(s): i, j = 0, len(s) - 1 while i < j: if s[i] != s[j]: return False i += 1 j -= 1 return True ``` 3. **翻转字符串**：如给定一个字符串，将其原地翻转。两个指针分别从头尾开始，交换字符直到相遇。 ```python def reverse(s): left, right = 0, len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 ``` ### 快速排序与归并排序 - **快速排序**：基于分治策略的排序算法，使用“分区”操作将数组分为两个子序列，然后递归地对每个子序列进行排序。 - **归并排序**：也是分治策略，将数组分为两半，分别排序，然后合并两个已排序的子数组。 双指针在快速排序和归并排序中也有应用，如快速排序的“分区”操作可以使用双指针来实现，而归并排序的合并过程可以看作是两个有序数组的相向合并。 双指针算法在Python编程和算法设计中扮演着重要角色，无论是解决实际问题还是应对面试挑战，掌握双指针技巧都能显著提高解题效率。通过灵活运用同向和相向双指针，可以解决各种复杂问题，实现高效的算法设计。