免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

我認(rèn)為雙指針技巧還可以分為兩類，一類是「快慢指針」，一類是「左右指針」。前者解決主要解決鏈表中的問(wèn)題，比如典型的判定鏈表中是否包含環(huán)；后者主要解決數(shù)組（或者字符串）中的問(wèn)題，比如二分查找。

一、快慢指針的常見(jiàn)算法

快慢指針一般都初始化指向鏈表的頭結(jié)點(diǎn) head，前進(jìn)時(shí)快指針 fast 在前，慢指針 slow 在后，巧妙解決一些鏈表中的問(wèn)題。

1、判定鏈表中是否含有環(huán)

這應(yīng)該屬于鏈表最基本的操作了，如果讀者已經(jīng)知道這個(gè)技巧，可以跳過(guò)。

單鏈表的特點(diǎn)是每個(gè)節(jié)點(diǎn)只知道下一個(gè)節(jié)點(diǎn)，所以一個(gè)指針的話無(wú)法判斷鏈表中是否含有環(huán)的。

如果鏈表中不含環(huán)，那么這個(gè)指針最終會(huì)遇到空指針 null 表示鏈表到頭了，這還好說(shuō)，可以判斷該鏈表不含環(huán)。

但是如果鏈表中含有環(huán)，那么這個(gè)指針就會(huì)陷入死循環(huán)，因?yàn)榄h(huán)形數(shù)組中沒(méi)有 null 指針作為尾部節(jié)點(diǎn)。

經(jīng)典解法就是用兩個(gè)指針，一個(gè)每次前進(jìn)兩步，一個(gè)每次前進(jìn)一步。如果不含有環(huán)，跑得快的那個(gè)指針最終會(huì)遇到 null，說(shuō)明鏈表不含環(huán)；如果含有環(huán)，快指針最終會(huì)超慢指針一圈，和慢指針相遇，說(shuō)明鏈表含有環(huán)。

2、已知鏈表中含有環(huán)，返回這個(gè)環(huán)的起始位置

這個(gè)問(wèn)題其實(shí)不困難，有點(diǎn)類似腦筋急轉(zhuǎn)彎，先直接看代碼：

可以看到，當(dāng)快慢指針相遇時(shí)，讓其中任一個(gè)指針重新指向頭節(jié)點(diǎn)，然后讓它倆以相同速度前進(jìn)，再次相遇時(shí)所在的節(jié)點(diǎn)位置就是環(huán)開(kāi)始的位置。這是為什么呢？

第一次相遇時(shí)，假設(shè)慢指針 slow 走了 k 步，那么快指針 fast 一定走了 2k 步，也就是說(shuō)比 slow 多走了 k 步（也就是環(huán)的長(zhǎng)度）。

設(shè)相遇點(diǎn)距環(huán)的起點(diǎn)的距離為 m，那么環(huán)的起點(diǎn)距頭結(jié)點(diǎn) head 的距離為 k - m，也就是說(shuō)如果從 head 前進(jìn) k - m 步就能到達(dá)環(huán)起點(diǎn)。

巧的是，如果從相遇點(diǎn)繼續(xù)前進(jìn) k - m 步，也恰好到達(dá)環(huán)起點(diǎn)。

所以，只要我們把快慢指針中的任一個(gè)重新指向 head，然后兩個(gè)指針同速前進(jìn)，k - m 步后就會(huì)相遇，相遇之處就是環(huán)的起點(diǎn)了。

3、尋找鏈表的中點(diǎn)

類似上面的思路，我們還可以讓快指針一次前進(jìn)兩步，慢指針一次前進(jìn)一步，當(dāng)快指針到達(dá)鏈表盡頭時(shí)，慢指針就處于鏈表的中間位置。

當(dāng)鏈表的長(zhǎng)度是奇數(shù)時(shí)，slow 恰巧停在中點(diǎn)位置；如果長(zhǎng)度是偶數(shù)，slow 最終的位置是中間偏右：

尋找鏈表中點(diǎn)的一個(gè)重要作用是對(duì)鏈表進(jìn)行歸并排序。

回想數(shù)組的歸并排序：求中點(diǎn)索引遞歸地把數(shù)組二分，最后合并兩個(gè)有序數(shù)組。對(duì)于鏈表，合并兩個(gè)有序鏈表是很簡(jiǎn)單的，難點(diǎn)就在于二分。

但是現(xiàn)在你學(xué)會(huì)了找到鏈表的中點(diǎn)，就能實(shí)現(xiàn)鏈表的二分了。關(guān)于歸并排序的具體內(nèi)容本文就不具體展開(kāi)了。

4、尋找鏈表的倒數(shù)第 k 個(gè)元素

我們的思路還是使用快慢指針，讓快指針先走 k 步，然后快慢指針開(kāi)始同速前進(jìn)。這樣當(dāng)快指針走到鏈表末尾 null 時(shí)，慢指針?biāo)诘奈恢镁褪堑箶?shù)第 k 個(gè)鏈表節(jié)點(diǎn)（為了簡(jiǎn)化，假設(shè) k 不會(huì)超過(guò)鏈表長(zhǎng)度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

二、左右指針的常用算法

左右指針在數(shù)組中實(shí)際是指兩個(gè)索引值，一般初始化為 left = 0, right = nums.length - 1 。

1、二分查找

前文 二分查找算法詳解 有詳細(xì)講解，這里只寫最簡(jiǎn)單的二分算法，旨在突出它的雙指針特性：

2、兩數(shù)之和

直接看一道 LeetCode 題目吧：

只要數(shù)組有序，就應(yīng)該想到雙指針技巧。這道題的解法有點(diǎn)類似二分查找，通過(guò)調(diào)節(jié) left 和 right 可以調(diào)整 sum 的大?。?/p>

3、反轉(zhuǎn)數(shù)組

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

4、滑動(dòng)窗口算法

這也許是雙指針技巧的最高境界了，如果掌握了此算法，可以解決一大類子字符串匹配的問(wèn)題，不過(guò)「滑動(dòng)窗口」算法比上述的這些算法稍微復(fù)雜些。

幸運(yùn)的是，這類算法是有框架模板的，下篇文章就準(zhǔn)備講解「滑動(dòng)窗口」算法模板，幫大家秒殺幾道 LeetCode 子串匹配的問(wèn)題。