leetcode习题分类汇总-Two Pointers篇

Linked List Cycle-原地判断链表是否有圆圈

思路:fast-slow指针,只要存在cycle,fast最终会赶上slow;



Sort Colors-排序颜色,就是自己排序包含012三个数字的数组给出一遍遍历原地排序的解法

思路:91)双指针,快速排序的思想,两头往中间遍历。一遍遍历





### Remove Element-去除数组中的目标元素并返回长度·

思路:额,遍历一遍,维护一个next,把返回长度的数组顺序弄好就ok了,感觉木有什么意义啊…好像就是考察你如何在去除的同时记录长度,时间n。



Container With Most Water-计算最大容水量

思路:双指针遍历,当从两边向中间考虑时,乘水的面积是由(两端较小的高度)×(两个板之间的宽度)决定的。想要变得大一点,只有增加高度以期望超过宽度的减少。所以维护一个maxarea,然后不断增加高度以减少宽度的减少。时间N



Remove Duplicates from Sorted Array-去除数组的重复值并返回长度,不借助其他数据结构

思路:注意已经排序,快慢指针,快指针判断,慢指针填充,如果要返回数组的话copy一个,返回长度的话就是慢指针+1;时间N



Remove Duplicates from Sorted ArrayII-去除数组两次以上的重复值并返回长度

思路:维护一个counter和 idx,>3时跳过,A[idx++]=A[i]






### Linked List Cycle II-判断链表是否有循环,如果有返回循环开始的地方

思路:图网上一堆,所以说…链表的问题首先还是要画图

第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。

因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。

我们发现L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度。

2. 我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。



扩展问题:

1. 环的长度是多少?

2. 如何找到环中第一个节点(即Linked List Cycle II)?

3. 如何将有环的链表变成单链表(解除环)?

4. 如何判断两个单链表是否有交点?如何找到第一个相交的节点?





### Merge Sorted Array-合并两个有序数组,第一个数组有足够空间

思路:归并排序,只不过,因为防止元素被破坏逆向遍历。时间m+n





### Partition List-切分链表,把<x的节点放在左边,其他放在右边

思路:(1)依然是双指针,画图,找到第一个>=x的节点记录好,然后把左边所有<x的节点放在它左边。

(2)创建两个dummy1,dummy2节点,遍历一遍,cur1遍历dummy1存放<x的节点,cur2遍历dummy2存放>x的节点,最后两个节点连在一起即可,注意cur2.next要设置为null,否则就成为head循环了




### Remove Nth Node From End of List-去除链表的倒数第N个元素,尝试一次遍历搞定

思路:快慢指针,快指针先行N步骤,之后前后保持N的距离,fast到末尾后,slow skip掉下一个节点即可。



4. 3 Sum Closest-在数组中找到3个数字的和使其最靠近目标值

思路:一开始我以为用dfs,时间复杂度N2;后来发现用三个指针维护也行,当前,next,已经从最后一个元素开始向前的指针,时间复杂度貌似也是N2,两个内循环;



Minimum Size Subarray Sum-给定数组和目标值求长度最小且不小于目标值的自数组。

思路:(1)两个指针遍历数组,维护长度最小值,时间O(N);




### Implement strStr()- 判断一个字符串是否是另一个字符串的子串。

思路:这个题目最经典的算法应该是KMP算法,Knuth–Morris–Pratt algorithm。KMP算法是最优的线性算法,复杂度已经达到这个问题的下限。但是KMP算法比较复杂,很难在面试的短时间里面完整正确的实现。所以一般在面试中并不要求实现KMP算法。

采用brute force的算法,假设原串的长度是n,匹配串的长度是m。思路很简单,就是对原串的每一个长度为m的字串都判断是否跟匹配串一致。总共有n-m+1个子串,所以算法时间复杂度为O((n-m+1)m)=O(nm),空间复杂度是O(1)。

### Valid Palindrome-判断是否为回文串

思路:把其他符号大小写都去掉然后reverse,判断是否equals即可

 

### Rotate List-翻转链表k个体位

思路:还是利用fast-slow指针,fakehead等常见手法,写烂了…只是主要要用k%i判断k是否大于链表的长度i;



ThreeSum-数组中寻找三个数的和等于0

思路:这题就是比3sum closest 多考虑一个去重问题,因为排好序了所以也简单,1.利用两个指针寻找sum; 2.去重 时间N2




4Sum-数组中寻找4个数的组合之和等于目标值,要求无重复的列出 思路 :跟3 sum差不多,只是需求扩展到四个的数字的和了。我们还是可以按照3 sum中的解法,只是在外面套一层循环,相当于求n次3 sum。我们知道3 sum的时间复杂度是O(n^2),所以如果这样解的总时间复杂度是O(n^3)。


(2)hashtable,具体未展开了解…

扩展:k-sum问题


总结数组的遍历,去重,极值问题,链表的切分,链接问题,字符串的匹配很多问题都和双指针相关,这类题目往往难度不是很大,双指针的目的常常在于减少时间和空间复杂度,难度并不是很大。