破解编码面试：第 3 部分 – 两指针技术
在本系列的第 2 部分中，我们讨论了滑动窗口模式，它有助于有效解决涉及连续子数组或子字符串的问题。在第 3 部分中，我们将探讨编码面试中的另一个基本模式：双指针技术。这种技术对于涉及数组、链表或字符串的问题特别有效，其中比较或配对元素是关键。
在我们开始之前，如果您正在寻找准备编码面试的综合指南，请考虑阅读《破解编码面试》，这是任何认真想在顶级科技公司找到工作的人的必备书籍。
两指针技术概述
双指针技术是一种简单但功能强大的方法，其中两个指针（或索引）用于迭代数据结构，通常以相反的方向或以不同的速度移动。此模式对于涉及以下问题特别有用：
- 配对元素
- 搜索组合（例如两个数字相加为目标值）
- 比较数组或列表两端的元素
- 检测循环或回文
通过同时移动两个指针，这种方法减少了对嵌套循环的需求，将暴力解决方案转变为更高效的解决方案，时间复杂度低至o(n)。
何时使用两指针技术：
- 输入已排序（或可以排序）。
- 您需要找到元素对（例如，加起来等于目标的数字对）。
- 您需要检测或比较元素之间的属性（例如回文检查、链表循环）。
- 问题可以分为两个子问题（比如从数组的两端搜索）。
两种指针方法的类型
1. 两个相反方向的指针
它是什么：两个指针从数组或列表的两端开始，向彼此移动并在中间相遇。
示例问题：给定一个排序数组，找到两个数字相加达到特定目标。
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # move the left pointer to the right.
else:
right -= 1 # move the right pointer to the left.
return [] # return an empty list if no pair is found.
说明：
- 指针从数组的两端开始。
- 如果指针处的两个元素之和小于目标，则将左指针向右移动（以增加总和）。
- 如果总和较大，请将右指针向左移动（减少总和）。
- 这将潜在的 o(n²) 强力搜索减少为 o(n)。
2. 两个指向同一方向的指针
它是什么：两个指针以相同的方向移动，但速度不同。这对于检测循环（例如链表中的循环）或查找序列中的特定条件等问题很有用。
示例问题：检测链表中的循环（floyd 龟兔赛跑算法）。
class listnode:
def __init__(self, value=0, next=none):
self.value = value
self.next = next
def has_cycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next # move slow pointer by 1 step.
fast = fast.next.next # move fast pointer by 2 steps.
if slow == fast:
return true # cycle detected.
return false # no cycle detected.
说明：
- 慢指针每次移动一步，快指针移动两步。
- 如果存在循环，快指针最终会追上慢指针。
- 这将循环检测问题从 o(n²) 减少到 o(n)。
实现两个指针解决方案的步骤
初始化指针：通常，这涉及在开头启动一个指针，在结尾启动另一个指针（对于相反方向），或者同时在开头启动另一个指针（对于相同方向）。
定义条件：指针的移动取决于问题。根据解决方案的当前状态确定何时移动每个指针以及向哪个方向移动。
更新结果： 在每一步中，检查您正在优化的条件（例如求和、比较）。相应地更新结果。
停止条件：循环继续，直到两个指针相遇或交叉（相反方向），或者满足有效条件（相同方向）。
使用两指针技术的常见面试问题
1. 二和（排序数组）
问题：给定一个排序的整数数组，找到两个数字相加达到给定的目标。
解决方案：使用数组开头和结尾的两个指针，根据总和调整指针。
2. 盛水最多的容器
问题：给定一个高度数组，找到与 x 轴一起形成一个容器的两条线，使得该容器包含最多的水。
模式： 在数组的两端使用两个指针。将高度较小的指针向内移动以最大化区域。
3. 回文检查
问题：给定一个字符串，判断它是否是回文。
模式：使用两个指针，一个在字符串的开头，一个在字符串的末尾，在比较字符时向内移动。
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False # Characters do not match.
left += 1
right -= 1
return True # All characters matched, so it's a palindrome.
面试的两个技巧
- 从排序数组开始：对数组进行排序可以更轻松地实现两指针，特别是在像两个和这样的配对问题中。
- 从比较的角度思考：无论是比较字符串中的字符还是数组中的元素，始终检查应该在什么条件下移动每个指针。
- 使用暴力进行可视化： 首先考虑暴力解决方案，然后寻找两个指针可以利用的模式，以避免不必要的比较。
- 仔细检查边界： 注意边缘情况，尤其是当指针相遇或重叠时。
结论
双指针技术是解决各种编码面试问题的高效方法，特别是那些涉及比较、配对或序列循环的问题。通过掌握这项技术以及滑动窗口模式，您将有能力处理许多面试场景。
在本系列的下一部分中，我们将探索编码面试中的另一个基本模式：快慢指针技术，这对于检测循环和查找中间元素特别有用。
敬请期待第 4 部分！
