程序猿养成之路：LeetCode双指针典型题目

2021-03-06

算法解释

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

若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的
区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是
排好序的。

对于C++中指针的一些知识（常量指针、指针常量、函数指针、指针函数等等），有兴趣的读者可以自行了解，

我之前写过一篇指针常量与常量指针

典型题目

LeetCode NO.167 Two Sum II - Input array is sorted(EASY)

题目描述

Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in increasing order.
-1000 <= target <= 1000
Only one valid answer exists.

题目分析

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

如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元
素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元
素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。

可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最
优解的两个数的位置分别是l 和r。我们假设在左指针在l 左边的时候，右指针已经移动到了r；
此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达l。同理，如果我们假设
在右指针在r 右边的时候，左指针已经移动到了l；此时两个指针指向值的和大于给定值，因此
右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于$(l,r)$之间，又因为不满足条
件时指针必须移动一个，所以最终一定会收敛在l 和r。

题解

vector<int> twoSum(vector<int>& numbers, int target) {
   int i = 0, j = numbers.size()-1;
   int sum = 0;
   while(i<j){
       sum = numbers[i] + numbers[j];
       if(target == sum)  
           return vector<int> {++i,++j};
       else if(sum < target)    
           ++i;
       else --j;
   }
   return vector<int>(2);
}

LeetCode NO.88 Merge Sorted Array(EASY)

题目描述

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

nums1.length == m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-109 <= nums1[i], nums2[i] <= 109

题目分析

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

我们利用i 和j 当作两个数组的指针，再额外创立一个curr指针，起
始位置为m+n-1。每次向前移动i或j的时候，也要向前移动curr。这里需要注意，如果nums1
的数字已经复制完，不要忘记把nums2 的数字继续复制；如果nums2 的数字已经复制完，剩余
nums1 的数字不需要改变，因为它们已经被排好序。

题解

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i=m-1,j=n-1,curr = m+n-1;
    while(i>=0 && j>=0) 	nums1[curr--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    while(j>=0)    nums1[curr--] = nums2[j--];
    return;
}

LeetCode NO.142 Linked List Cycle II(MEDIUM)

题目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

题目分析

对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针，
分别命名为slow 和fast，起始位置在链表的开头。每次fast 前进两步，slow 前进一步。如果fast
可以走到尽头，那么说明没有环路；如果fast 可以无限走下去，那么说明一定有环路，且一定存
在一个时刻slow 和fast 相遇。当slow 和fast 第一次相遇时，我们将fast 重新移动到链表开头，并
让slow 和fast 每次都前进一步。当slow 和fast 第二次相遇时，相遇的节点即为环路的开始点。

题解

ListNode *detectCycle(ListNode *head) {
	ListNode *slow = head, *fast = head;
	// 判断是否存在环路
	do {
		if (!fast || !fast->next) return nullptr;
		fast = fast->next->next;
		slow = slow->next;
	} while (fast != slow);
	// 如果存在，查找环路节点
	fast = head;
	while (fast != slow){
		slow = slow->next;
		fast = fast->next;
	}
	return fast;
}

理论分析

在这里插入图片描述

将设链表起始点到环入口长度为a，环长为r，在快指针进入到环到慢指针进入环前的这段时间，也许快指针已经走了好几圈。然后慢指针进入环，设慢指针和快指针相遇时，慢指针在环内走了X步，走的总步数为S步

$S = a+X$

此时快指针在环内走了n圈加X步，即快指针总步数为

$S’ = nr+X+a$

由于快指针走的总步数为慢指针走的总步数的两倍，所以

$nr+X+a=2(X+a)$

整理得

$X+a=nr$

即

$a=nr-X=(n-1)r+r-X$

结论：环入口距离起点的距离（a）和相遇点距离环入口的距离（r-x）相差整数倍的r.

故让慢指针回到起点，快指针从相遇点开始继续走，步长都为1，则两者再相遇时，即为环入口。