LeetCode two-pointer 问题总结

2017-03-06

记录 LeetCode 上有关 two-pointer 问题的题解

n-Sum 系列

1. Two Sum 一个比较好的解法是使用哈希表。思路如下: 维持一个哈希表,key 为元素的值,value为元素的下标。依次遍历元素,去哈希表找目标值与当前元素的差值,找到了则记录下来,否则继续进行循环。每一循环都将当前元素的值与下标加入到哈希表中。总体思路时间复杂度为:$O(n)$

167. Two Sum II - Input array is sorted 在输入数组的已经排序的情况下,这时可以使用两个指针:头指针指向数组头,尾指针指向数组尾。然后根据两个指针指向元素之和与目标值的大小动态调整,当两指针相遇时,算法停止。总体思路时间复杂度为:$O(n)$

15. 3Sum 这个可以用 Two Sum 的思想考虑。但是呢,因为题目要求不能有重复的组合。所以,我们可以首先考虑对数组排序,然后固定一个数,使用前后两个指针扫描。当两个指针重复时,这时把第一个数往前移动,重复上述步骤。注意要处理重复数字的情况。总体时间复杂度为:$O(n^2)$

16. 3Sum Closest 这道题和 3Sum 思路类似,仍是先排序,然后固定一个数,使用前后指针进行扫描。不过在移动指针前,需要将当前三个数之和与 target 进行比较,获得最接近的数。总体时间复杂度为:$O(n^2)$

18. 4Sum 这道题依然类似于 3Sum,先排序,然后固定一个数,剩下就可以用 3Sum 的思路解决了。要注意重复数字的处理。总体时间复杂度为:$O(n^3)$

总结,对于 n-Sum 问题,参考上面的做法:可以先进行排序,然后固定第一个数,那么就变成 (n-1)-Sum 问题;这样一直重复,直到变成 2-Sum 问题就可以很好的解决了。在这过程中,要注意重复数字问题的处理。总的来说,这算是减治法的应用了。

链表有环系列

141. Linked List Cycle 这道题比较有趣,可以使用两个指针,fast 和 slow,fast 每次前进两步,slow 每次前进一步。如果链表存在环,那么 fast 和 slow 一定会相遇,否则的话 fast 则会先到达链表尾部。

142. Linked List Cycle II 这道题不仅要求找出链表是否有环,如果有环的话,还要找出环的起始点。判断环是否存在可以使用 No. 141 的思路,如果链表有环的话,并且环有 n 个结点。使用双指针,先让指针 a 走 n 步,然后让指针 b 指向链表头,并让两个指针以相同速度前进。当两个指针相遇时,当前节点就是链表环的入口了。

数组交叉系列

349. Intersection of Two Arrays 要使用双指针的话,可以先对两个数组都进行排序,然后分别对每一个数组都用一个指针指向,同时进行扫描。

另一个方法是使用集合来解决。先对第一个数组进行扫描,将所有元素加入集合。然后对第二个数组进行扫描,判断当前元素是否在集合中,如果在就加入结果集中。对第二个数组进行扫描时要注意去重。

350. Intersection of Two Arrays II 类似地,可以用 No. 349 排序加双指针的方法解决。 另一个方法是使用一个哈希表。先对第一个数组进行扫描,记录数字和对应出现频率。接着对第二个数组进行扫描,判断该数字是否出现哈希表中,并且频率大于0。如果是,那么就可以加入结果集中,并将对应对应频率减1;否则就不行。

从排序数组中删除重复元素系列

26. Remove Duplicates from Sorted Array 这题思路有点类似于 No. 27 题。指针 a 指向新数组的尾部,指针 b 指向数组元素,每次将指针 b 的值赋给指针 a,然后 b 一直跳过 duplicate 直到找到下一个数。当 b 遍历到数组尾部时,指针 a 所在位置就是新数组长度了。

80. Remove Duplicates from Sorted Array II 一个解法是遍历所有数组元素,将那些没有被包含两次的元素加入结果集中。参考这里:3-6 easy lines, C++, Java, Python, Ruby 另一种解法类似于上面 No. 26 题,不过指针 b 可以多赋值一次 duplicate 给指针 a 再前进。不过,奇怪的是有一个测试用例在本地和 Run Code 上都可以通过,但是提交结果就是过不了,参考这里:A very strange problem

其他

Easy

345. Reverse Vowels of a String 这道题可以使用一个头指针指向字符串头,一个尾指针指向字符串尾;移动头指针找到元音字母,尾指针同理,然后交互两指针所指元素。重复上述步骤直到两指针重叠。时间复杂度为:$O(n)$

125. Valid Palindrome 用头尾指针解决,注意要跳过非字符、数字并且将大写字母转成小写字母。时间复杂度为:$O(n)$

283. Move Zeroes 用两个指针,假设一个指针指向一个非零数,位置为 i;另一个指针指向零,位置为 j。要求 j <i 而且位置 j 以前只有非零数,这时交换两者位置。重复上述过程,直到指向非零数的指针到达数组尾。时间复杂度为:$O(n)$

88. Merge Sorted Array 这道题我们可以考虑从两个数组的尾部开始合并,这样就不需要移动数组来制造空间了。时间复杂度为:$O(m+n)$

234. Palindrome Linked List 因为题目要求为 O(1) 空间,所以考虑将链表前半部分或者后半部分反转,然后再进行判断。可以参考 No. 141 的思路,使用 fast 和 slow 指针;fast 每次走两部,slow 每次走一步。当 fast 走到链表尾部时,那么 slow 就走到链表中间了,这时就可以进行反转了。反转之后再进行判断就比较容易了。

344. Reverse String 使用头指针指向字符串头,尾指针指向字符串尾,然后依次交换两指针内容,直到两指针重叠。

28. Implement strStr() 使用双指针的话,就是挨个比较了。先找到使得两个字符串首字符相等的位置,然后继续比较下面的字符。这样的话,hatstack 每次前进步长为 1。当然也可以使用 KMP 算法,这样可以获得更大的前进步长。

27. Remove Element 一种方法是使用两个指针,指针 a 指向新数组尾,指针 b 指向当前正在遍历的元素。如果指针 b 所指元素不等于 val,那么就将这个元素赋值给指针 a,之后调整指针位置。完成遍历后,a 的位置就是新数组的长度了。 因为这里不要求保持数组原有顺序,另一个思路是使用头尾指针,头指针的值为 val,尾指针的值不为 val,交换两指针元素,然后重复上面步骤直到两指针相遇。如果要求保留数组顺序,那么思路可以类似于 No. 283 题。

532. K-diff Pairs in an Array 一个简单的方法是先对数组排序,然后使用双指针。固定指针 a,其所指元素为 i,接着从 a+1 处开始查找 i+k 是否在数组中。指针前进过程中要注意跳过重复元素,当指针 a 到达数组尾时,算法结束。

另一个方法是使用集合和哈希表。首先遍历数组,使用哈希表记录下元素和对应出现频率,频率上限为2。然后遍历数组,针对每一个元素 n,判断 n 是否在集合中,如果不在,那么接下来计算 target = n+k,并判断 n 和 target 是否相等,如果相等,先将 n 对应频率减 1。接着判断 target 是否在哈希表中并且对应频率大于 0,如果都满足,那么可以将结果加 1,并将 target 对应频率减 1。每当遍历一个元素,当要将该元素加入集合中。注意,当 k 小于 1 时,应该直接返回 0。

287. Find the Duplicate Number 这个可以用二分法来解决。二分法的关键在于找出搜索空间:

  1. 一种情况是数组已经排序,这时可以用下标作为搜索空间
  2. 另一种就是这种了,数组未排序,但是知道元素范围,这时就可以使用元素范围作为搜索空间

回到这道题,使用二分法,将下限设为 1,上限设为 n,然后计算数组元素中值超过 mid 的元素个数 count,如果 count 小于等于 mid,说明 duplicate 存在于 [mid+1, hi] 范围内;否则则存在于 [lo, mid] 范围内。

19. Remove Nth Node From End of List 这道题和剑指 offer 中面试题 15:链表中倒数第 k 个结点有点类似,不过这里是删除倒数第 N 个结点,但是思路是一样的。先让一个指针 a 走 n 步,然后将另一个指针 b 指向链表头,接着两个指针同时开始走。当指针 a 走到链表尾时,指针 b 走到倒数第 n+1 个结点,这时就可以进行删除了。要注意考虑边界情况。

11. Container With Most Water 用两个指针,头指针为 i,尾指针为 j。刚开始时,容积容量最大为 (j-i)*min(height[i],height[j])。这时,因为头指针只能加,尾指针只能减,导致底部长变小,所以这时要想增加容器容量,只能增加容器最矮一边的高度了。于是,可以固定容器较高一边的指针,移动容器较矮一边的指针,直到找到另一个更高的边,这时再计算容器容量,并与当前最大容器容量进行比较。当两个指针相遇时,算法结束。

Medium

209. Minimum Size Subarray Sum 使用双指针。用 minLen 表示当前最小子数组长度,初始值为数组长度。指针 a 向前走,直到元素累积和大于等于 s,记录当前子数组长度,并与 minLen 比较。当指针 a 停下时,指针 b 开始走,每走一步累积和就减去指针 b 所指元素,直到累积和小于 s,这时在记录当前子数组长度,并与 minLen 比较(之所以这么做,是因为指针 b 向后退一步,那么累积和刚好大于等于 s)。当指针 a 到达数组尾时,算法结束。实现时要注意如何计算子数组长度,并且要处理当数组所有元素之和都小于 s 的情况(可以用一个 Flag 判断)

3. Longest Substring Without Repeating Characters 可以使用一个哈希表来做,哈希表存储字符和对应下标。每次扫描一个新字符,判断其是否在哈希表中。如果不在,说明不是重复字符,可以继续;如果在,说明是重复字符,但是这里要判断这个重复字符是否被包含在当前子字符串中,如果不在,仍然跳过;如果在,则要计算旧子字符串的长度并重新设置新子字符串的起始位置。每次扫描字符,都要更新哈希表。当然,因为这里只有 ASCII 码,可以用向量代替哈希表。

86. Partition List 仍然使用双指针,指针 a->next 总是指向第一个大于等于 x 的元素,指针 b->next 在 a->next 后面,总是指向小于 x 的元素,每次将 b->next 插入到 a->next,然后各自前进一步。当指针 b->next 到达链表尾,算法结束。一开始时可以加上一个哨兵比较好实现。

61. Rotate List 注意,k 可能大于链表长度,所以一开始需要遍历链表,求出链表长度 len,然后对 k 用 len 取模,即 k = k % len。接着,使用指针找出这样的结点:其后面是需要旋转的 k 个结点,然后就可以进行旋转了。注意考虑边界条件和指针非空的判断。

待续…