玩转双指针

Posted on

算法解释

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针：

  • 若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。
  • 若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。

在 C++ 中，要注意 const 的位置对指针效果的影响：

1
2
3
4
5
int x;
int * p1 = &x; // 指针可以被修改，值也可以被修改
const int * p2 = &x; // 指针可以被修改，值不可以被修改 (const int)
int * const p3 = &x; // 指针不可以被修改 (* const)，值可以被修改
const int * const p4 = &x; // 指针不可以被修改，值也不可以被修改

Two Sum

167. Two Sum II - Input Array Is Sorted
因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。

归并两个有序数组

88. Merge Sorted Array
因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m−1 位和 nums2 的 n−1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。

a++ 和 ++a 都是将 a 加 1，但是 a++ 返回值为 a，而 ++a 返回值为 a+1。如果只是希望增加 a 的值，而不需要返回值，则推荐使用 ++a，其运行速度会略快一些。

滑动窗口

76. Minimum Window Substring
本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。

快慢指针

142. Linked List Cycle II
对于链表找环路的问题，有一个通用的解法——Floyd 判圈法。

对于某些只需要判断是否存在环路的题目，也可以通过建造哈希表来查重。

练习

633. Sum of Square Numbers
Two Sum 题目的变形题之一。

680. Valid Palindrome II
Two Sum 题目的变形题之二。

524. Longest Word in Dictionary through Deleting
归并两个有序数组的变形题。

340. Longest Substring with At Most K Distinct Characters
需要利用其它数据结构方便统计当前的字符状态。