刷題常用技巧(二)-雙指針方法

前言

雙指針的技巧是我在刷題時覺得”So brilliant!”的方法，可以有效的將時間複雜度降低，而且在刷題上即便不是在考雙指針的用法，也常常可以套用雙指針的邏輯去思考，那就讓我們來看看這個方法吧！

原理

我認為簡單來說可以看成

“存取兩個變數，讓這兩個變數不斷根據條件變動後做比較。“

用這方法常常最直接的優點就是省去了兩層迴圈的時間複雜度，然而，指針的設計也是有學問，練習到目前為止，常見的指針設計邏輯有三種

1. 同步，兩個指針一開始就指向不同的地方，如陣列中某數的左邊和右邊、陣列中的頭和尾。( 344. Reverse String (E))
2. 同步，兩個指針一開始指向同個地方，但是變動的速度不同，如一個動的快，一個動的慢，也可以稱為快慢指針。(287. Find the Duplicate Number (M))
3. 不同步，兩個指針指向同一個地方，但因為條件成立的與否，決定某一指針是否需要動。(80. Remove Duplicates from Sorted Array II(M))

應用

1. 反轉字串

反轉字串就是第一種設計邏輯很好的例子，可以先將字串轉成字元陣列，利用一個指標指向陣列頭部，一個指標指向陣列尾部，兩兩進行交換後，再個別往內縮一格即可完成字串反轉！

提供一個自己當初用雙指針的方法，判斷完奇偶數後從中間往左右兩邊跑，再兩兩交換即可達成反轉。

var reverseString = function(s) {
    if (s.length <= 1) return s
    //偶數
    if ((s.length & 1) === 0 ) {
        let l = s.length / 2 - 1
        let r = s.length / 2
        while( l >= 0 ) {
            [s[l], s[r]] = [s[r], s[l]]
            l--
            r++
        }  
    //奇數
    }else {
        let l = Math.floor(s.length / 2) - 1
        let r = Math.floor(s.length / 2) + 1
        while( l >= 0 ) {
            [s[l], s[r]] = [s[r], s[l]]
            l--
            r++
        }      
    }
}

2. 找到重複的值

這題因為題目有range [1, n]的特殊性，所以可以利用快慢指標來解，當初研究快慢指標的時候覺得這方法很酷。利用龜兔賽跑的概念，兔子的速度是烏龜的兩倍，若兩人能相遇代表有圈(有重複的值)，而相遇時，兔子走過的距離是烏龜的兩倍，如下圖

烏龜走過的距離是: S = m + n + aC (a代表走了幾圈)

兔子走過的距離是: 2S =m + n + bC (b代表走了幾圈，距離是烏龜的兩倍)

將兩式相減可得 S = (b - a)C，而又 S = m + n + aC ，

故可推得(b - a)C = m + n + aC => (b - 2a)C = m + n，

代表m + n的距離是一圈距離的整數倍，若相遇時讓烏龜從頭開始走，且兔子和烏龜開始以一樣速度前進，當烏龜走了m距離走到環起點，兔子也走了m距離，而兔子原先的位置距離環起點就為n，故再走了m距離，即為m+n，也就是圈的整數倍(前面推導而得)，即兔子也到了圈的起點！

附上此題的程式碼

var findDuplicate = function(nums) {
    // p1走一步 p2走兩步
    let p1 = nums[0]
    let p2 = nums[nums[0]]
    //當p1與p2不相等 繼續走
    while (p1 ^ p2) { 
        p1 = nums[p1]; p2 = nums[nums[p2]]
    }
    //相遇時 讓p1退回起點 此時相距環的整數倍 直到再次相遇即為起點
    p1 = 0
    while (p1 ^ p2) {
        p1= nums[p1]; p2=nums[p2]
    }
    return p1
}

3. 去除重複的值

讓兩指標指向同個位子，但是可以利用條件判斷來讓指標決定變動與否，如下面這個例子，利用指標1當作”寫”指標，指標2當作”讀”指標，讓指標2去遍歷整個陣列，只要讀到與指標1前兩個位置(pointer1 - 2)的值不同，則將指標2讀到的值寫入指標1的位置，同時指標1再往下一格移動，如此一來就能確保重複的數只會出現兩次。需要注意的是，這題的陣列要先排序過。

var removeDuplicates = function(nums) {
    let pointer1 = 2
    for (let pointer2 = 2; pointer2 < nums.length; pointer2++) {
        if (nums[pointer1 - 2] !== nums[pointer2]) {
            nums[pointer1] = nums[pointer2]
            pointer1++
        }
    }
//題目要求回傳陣列長度，因pointer1指的是位置，指向最後一位時實際上就是所求陣列長度
return pointer1
};