82. 刪除排序鏈表的重復元素

力扣傳送：
https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

為雙湖等地區(qū)用戶提供了全套網頁設計制作服務，及雙湖網站建設行業(yè)解決方案。主營業(yè)務為網站設計制作、做網站、雙湖網站設計，以傳統(tǒng)方式定制建設網站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

給一個排好序的鏈表，刪除把鏈表中出現的所有的重復的項：
1 2 2 3 3 3 4 5 ----->1 4 5

這道題有很多種解法，我第一眼看到這題的時候，想到了 哈希表。
利用哈希表來記錄出現的重復的節(jié)點元素，接著在遍歷鏈表，等到這個節(jié)點出現在了哈希表中，則while 循環(huán)一直跳過這個節(jié)點，直到跳到下一個不同的元素為止。

---

哈希表的做法:

1. 首先遍歷一邊鏈表，記錄下哈希表的數據
2. 然后再遍歷一遍鏈表，當哈希表記錄的此節(jié)點處的值出現的次數大于一次時，一直while找到直到下一個等于一次的節(jié)點位置，然后連接前一個節(jié)點位置，這樣就做到了跳過了出現次數大于二的節(jié)點的中間節(jié)點。
3. 雙指針分別連接鏈表節(jié)點。

class Solution {public:
    ListNode* deleteDuplicates(ListNode* head) {unordered_mapm;
        ListNode* temp=head;
        while (temp)
        {	//首先初始化哈希表，記錄下每個節(jié)點的值出現的次數
            m[temp->val]++;
            temp=temp->next;
        }
        ListNode* pDummy=new ListNode{-101,head};
        ListNode* slow=pDummy;
        ListNode* fast=head;
        while (fast && fast->next)
        {if (m[fast->val]>1)
            {ListNode* pTemp=fast->next;
                while (fast && m[fast->val]>1)
                {fast=fast->next;
                }
                slow->next=fast;
            }
            else
            {slow=slow->next;
                fast=fast->next;
            }
        }
        return pDummy->next;
    }
};

哈希表的缺點：
我們的哈希表的空間隨著鏈表的增大而增大，空間復雜度達到了O（N）。

但其實我們沒必要使用哈希表。
我們知道用哈希表來記錄出現次數大于一次的節(jié)點，那我們能不能直接用雙指針的快指針來記錄呢？ 只需要合適的邊界檢測，就可以記錄下其快指針的 當前節(jié)點元素和 下一個節(jié)點元素的值，判斷他們是否相等即可。

實現：

1. 啞節(jié)點方便返回鏈表（pDummy）
2. 慢指針在前，快指針在后，快指針移動一步，每次快指針都判斷它當前的值和后面的值想不想等，如果相等，則快指針進入while循環(huán)，一直跳過。
3. 等到處理完畢后， 慢指針前進一步，等于快指針；快指針再前進一步，等于next

class Solution {public:
    ListNode* deleteDuplicates(ListNode* head) {ListNode* pDummy=new ListNode{-101,head};
        ListNode* slow=pDummy;
        ListNode* fast=head;
        while (fast && fast->next)
        {int val=fast->val;
            if (val==fast->next->val)
            {while (fast && fast->val==val)
                {fast=fast->next;
                }
                slow->next=fast;
            }
            else
            {slow=fast;
                fast=fast->next;
            }
        }
        return pDummy->next;
    }
};

時間復雜度：O（N）只遍歷鏈表一遍，空間復雜度：O（1）

---

15. 三數之和

力扣傳送門：
https://leetcode.cn/problems/3sum/description/?envType=study-plan&id=suan-fa-ji-chu&plan=algorithms&plan_progress=y00ve32

找到數組中是否包含三個元素使得 nums[i]+nums[j]+nums[z] =0

這道題目一看看出就可以使用暴力搜索的做法：首先給數組排序，然后創(chuàng)建一個三重循環(huán)，每重循環(huán)遍歷每一個元素；注意，我們的元素可能會出現重復項，因此我們要跳過兩重循環(huán)中可能遍歷到的重復的項：

class Solution {public:
    vector>threeSum(vector& nums) {vector>res;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for (int i=0;iif (i==0 || nums[i]!=nums[i-1])
            {for (int j=i+1;jif (j==i+1 || nums[j]!=nums[j-1])
                    {for (int z=j+1;zif (z==j+1 || nums[z]!=nums[z-1])
                            { if (nums[i]+nums[j]+nums[z]==0)
                                {res.push_back({nums[i],nums[j],nums[z]});
                                }
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
};

我們的時間復雜度達到了O（N^3） 這對于最長數據量3000來說是很容易超時的，因為 3000 * 3000 * 3000 相乘后達到了27,000,000,000，即這就是三重循環(huán)的最壞的情況，因此暴力搜索的方法無法通過。

---

我們引入一個新方法：

利用雙指針降低維數： 利用雙指針把三重循環(huán)降低為二重循環(huán)。

1. 當我們確定第一個數字之后，如果第二個數字增大，則第三個數字必定減小。
2. 令第二個數字和第三個數字同時尋找。
3. 第二個數字起始位于第二重循環(huán)的開頭，第三個數字起始位于第二重循環(huán)的末尾。

我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個從數組最右端開始向左移動的指針

class Solution {public:
    vector>threeSum(vector& nums) {int n=nums.size();
        vector>res;
        sort(nums.begin(),nums.end());
        for (int i=0;i//當前項和前一項相同，則當前數字已經被剛才用過了，則直接跳過這個數字
            if (i>0 && nums[i]==nums[i-1])
            {continue;
            }
            //第二重循環(huán)同時遍歷 j 和 z
            int z=n-1;  //初始化z的位置，z從后往前
            for (int j=i+1;j//同理，跳過重復的數字
                if (j>i+1 && nums[j]==nums[j-1])
                {continue;
                }
                //同時需要保證j0)
                {//因為序列從小到大排序，當前的結果大于0，則減小z,尋找合適的位置
                    --z;
                }
                //如果j 和 z相遇，則表示無論j再往后，z再往前，他們都不可能再有結果了（和為0），因為j再往后遍歷的數字一定和z之前的一個數字相同; z也是，一定和j之前的一個數字相同，我們已經遍歷過了，所以這種情況直接退出 
                if (j==z)
                {break;
                }
                if (nums[i]+nums[j]+nums[z]==0)
                {res.push_back({nums[i],nums[j],nums[z]});
                }
            }
        }
        return res;
    }
};

總結：

當我們需要枚舉數組中的兩個元素時，如果我們發(fā)現隨著第一個元素的遞增，第二個元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時間復雜度從 O(N^2)減少至 O(N)

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章名稱：算法進階：雙指針（一）c++leetcode例題-創(chuàng)新互聯
網頁URL：http://weahome.cn/article/pieig.html