刷題前必學！數組實戰-雙指針！用JavaScript學數據結構與算法详情 - javascript,算法,數據結構,數據結構和算法,程序員 HowieCong 日志

🧑‍💻JavaScript算法與數據結構-HowieCong

務必要熟悉JavaScript使用再來學！

一、兩數求和——Map

原題:

給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那兩個整數，並返回他們的數組下標。你可以假設每種輸入只會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。

示例：

給定 nums = [2, 7, 11, 15], target = 9\
因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

（1）暴力解題思路

暴力的解法：兩層循環來遍歷同一個數組；第一層循環遍歷的值為a，第二層循環遍歷的值為b；若a+b=目標值，那麼a和b對應的數組下標就是我們想要的答案
暴力的反思：
- 發現代碼兩層循環了，能不能用空間換時間，把它優化一層循環
- 兩層循環基本意味着O(n^2)的複雜度，這個複雜度容易導致算法超時，如果沒超時，寫了兩層遍歷，也會在面試時劃分與候選人的區別

（2）Map——空間換時間

結論：幾乎所有的求和問題，都可以轉化為求差問題

在遍歷數組的過程中，增加一個Map來記錄已經遍歷過的數字，及其對應的索引值，然後每遍歷到一個新數字的時候，都回到Map裏面查詢目標數與該數的差值是否已經在前面的數字中出現過了，若出現了，答案已經顯示，沒必要再往下走了
Eg：以nums = [2,7,11,15]這個數組為例，來模擬下思路
- 第一次遍歷到2，此時Map為空
- 以2為key，索引0為value作存儲，繼續往下走；遇到了7
- 計算targetnum和7的差值為2，去Map中檢索2這個key，發現是之前出現過的值
- 那麼2和7的索引組合就是這道題的答案
Map編碼實現

    const twoSum = function(nums,targer){
        // 用對象模擬map的能力
        const diffs = {}
        // 緩存數組長度
        const len = nums.length
        // 遍歷數組
        for(let i = 0; i < len; i++){
            // 判斷當前值對應的target差值是否存在（是否已經遍歷過）
            if(diffs[target - nums[i]] !== undefined){
                // 若有對應差值，那麼答案正確!
                return[diffs[target - nums[i]],i]
            }
            // 若沒有對應差值，則記錄當前值
            diff[nums[i]]=i
        }
    };

二、強大的雙指針

（1）合併兩個有序數組

原題：

給你兩個有序整數數組 nums1 和 nums2，請你將 nums2 合併到 nums1 中，使 nums1 成為一個有序數組。\
説明: 初始化 nums1 和 nums2 的元素數量分別為 m 和 n 。你可以假設 nums1 有足夠的空間（空間大小大於或等於 m + n）來保存 nums2 中的元素。

示例：

輸入:\
nums1 = [1,2,3,0,0,0], m = 3\
nums2 = [2,5,6], n = 3\
輸出:

[1,2,2,3,5,6]

1.思路分析

標準解法
- 首先定義兩個指針，各指向兩個數組生效部分的尾部
- 每次只對指針所指的元素進行比較，取其中較大的元素，把它從nums的末尾往前補充

為什麼要從後向前補充？

因為要所有值合併到nums1裏，所以我們這裏可以把nums1看作一個容器，這個容器不為空，而是前面幾個坑有內容，如果我們從前往後補充，就沒法直接往對應的坑位賦值了（會產生值覆蓋）

nums1的有效部分和nums2不一定是一樣長的，還得考慮其中一個提前到頭的這種情況：

如果提前遍歷完的是nums的有效部分，剩下的是nums2，那麼就意味着nums1的頭部空出來，直接把nums2補到nums1前面即可

如果提前遍歷完的是nums2，剩下的是nums1，由於容器本身就是nums，此時就不做任何額外的操作了

2.編碼實現

const merge = function(nums1,m,nums2,n){
    // 初始化兩個指針的動向，初始化nums1尾部索引k
    let i = m - 1, j = n - 1,k= m + n - 1
    // 當兩個數組都沒有遍歷完時，指針同步移動
    while(i >= 0 && j >= 0){
        // 取較大的值，從末尾往前填補
        if(nums1[i] >= num2[j]){
            nums1[k] = nums1[i]
            i--
            j--
        }else{
            nums1[k] = nums2[j]
            j--
            k--
        }
    }
    
    // nums2留下的情況，特殊處理
    while(j > 0){
        nums1[k] = nums2[j]
        k--
        j--
    }
}

（2）三數求和問題

原題：

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。\
注意：答案中不可以包含重複的三元組。

示例：

給定數組 nums = [-1, 0, 1, 2, -1, -4]，滿足要求的三元組集合為： [ [-1, 0, 1], [-1, -1, 2] ]

1.思路分析

可以把求和問題變成求差問題，固定其中一個數，在剩下的數尋找是否由兩個數和這個固定數相加是等於0的
雙指針使用場景 => 1.空間換時間 2.可以幫我們降低問題的複雜度
雙指針用在設計求和、比大小類的題目時，大前提往往是：該數組必須有序。否則雙指針根本無法幫助我們縮小定位的範圍
第一步就是將數組排序：

nums = nums.sort((a,b) =>{
    return a- b
})

第二步就是對數組進行遍歷，每次遍歷到哪個數字，就固定哪個數字，然後把左指針指向該數字後面的一個坑裏的數字，把右指針指向數組末尾，讓左右指針從起點開始，從中間前進

每次指針移動一次位置，計算以下兩個指針指向數字之和加上固定的那個數之後，是否等於0，如果是那麼我們就得到了一個目標組合；否則，分兩種情況來看：
- 相加之和大於0，説明右側的數偏大了，右指針左移
- 相加之和小於0，説明左側的數偏小了，左指針右移
這個數組在題目要求了“不重複的三元組”，還需要做一個重複元素的跳過處理

2.編碼實現

const threeSum = function(nums){
    // 用於存放結果數組
    let res = []
    // 給nums排序
    nums = nums.sort((a,b) =>{
        return a - b
    })
    // 緩存數組長度
    cosnt len = nums.length
    // 注意我們遍歷到倒數第三個數就足夠了，因為左右指針會遍歷後面兩個數
    for(let i = 0; i < len - 2; i++){
        // 左指針j
        let j = i + 1
        // 右指針k
        let k = len - 1
        // 如果遇到重複的數字，則跳過
        if(i > 0 && nums[i] === nums[i-1]){
            continue
        }
        while(j < k){
            // 三數之和小於0，左指針前進
            if(nums[i] + nums[j] + nums[k] < 0){
                j++
                // 處理左指針元素重複的情況
                while(j < k && nums[j] === num[j + 1]){
                    j++
                }
            }else if(nums[i] + nums[j] + nums[k] > 0){
                // 三數之和大於0，右指針後退
                k--
                //處理右指針重複的情況
                while(j < k && nums[j] === num[k + 1]){
                    k--
                }
            }else{
                // 得到目標數字組合，推入結果數組
                res.push(nums[i],nums[j],nums[k])
                // 左右指針一起前進
                j++
                k--
                // 若左指針元素重複，跳過
                while(j < k && nums[j] === num[j - 1]){
                    j++
                }
                // 若右指針元素重複，跳過
                while(j < k && nums[k] === num[k + 1]){
                    k--
                }
            }
        }
    }
    //  返回結果數組
    return res
}

（3）雙指針法中的“對撞指針”法

在上面的題，左右指針一起從兩邊往中間位置相互靠近，這樣的特殊雙指針形態，被稱為“對撞指針”

關鍵字——有序和數組
如果普通雙指針走不通，立刻要想到對撞指針
即使沒有“有序”，應該手動進行排序嘗試——沒有條件則創造條件
對撞指針可以幫助我們縮小問題的範圍，這點在上面的題可以看出，節省了計算時間，降低了問題本身的複雜度，做題的速度也快起來了

❓其他

1. 疑問與作者HowieCong聲明

如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！