[[428819]]

雙指針的算法原理，通過兩個指針在一個for循環下完成兩個for循環的工作。時間復雜度從優化到了。

雙指針的算法模板比較簡單，突破口主要是需要找到題目中的單調性，從而加以利用。

快慢指針

快慢指針一個鏈表操作技巧，它還有一個有趣的名字，龜兔賽跑。

• 移除元素：

class Solution { 
public: 
    int removeElement(vector<int>& nums, int val) { 
        int slowIndex = 0; 
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { 
            if (val != nums[fastIndex]) { 
                nums[slowIndex++] = nums[fastIndex]; 
            } 
        } 
        return slowIndex; 
    } 
}; 

• 環的入口位置：應用快慢指針，快指針走兩步，慢指針走一步。假使有環，兩指針遲早相遇;假使無環，快指針就會走到盡頭，退出循環。如果有環，慢指針重新開始，此時快指針是交點，同速兩指針交點必是入口。

class Solution { 
public: 
    ListNode *detectCycle(ListNode *head) { 
        ListNode* slow = head; 
        ListNode* fast = head; 
        while (fast && fast->next){ 
            fast = fast->next->next; 
            slow = slow->next; 
            if (fast == slow) break; 
        } 
         
        if (fast && fast->next){ 
            slow = head; 
            while(slow!=fast){ 
                slow = slow->next; 
                fast = fast->next; 
            } 
            return slow; 
        } 
        return nullptr; 
    } 
}; 

• 鏈表的中間結點：應用快慢指針，快指針走兩步，慢指針走一步。快指針走到盡頭時，慢指針剛好走了一半，返回即為中間結點。
• 刪除鏈表的倒數第 N 個結點：快指針先走 n 步，然后快慢指針同時走，快指針走到頭時，慢指針就在倒數第 n 個位置。

反向指針

反向指針經典題目是N sum 系列和二分變種題目。

N sum 系列的經典題目是：三數之和

def threeSum(nums): 
    nums.sort() 
    # [-4, -1, -1, 0, 1, 2] 
    res_list = [] 
    # 頭部循環查找 
    for i in range(len(nums)): 
     #  必須判斷 nums[i] > nums[i - 1]這個條件 
        if i == 0 or nums[i] > nums[i - 1]: 
            # 最左端 
            l = i + 1 
            # 最右端 
            r = len(nums) - 1 
            while l < r:  # 正在查找 
                three_sum = nums[i] + nums[l] + nums[r] 
                if three_sum == 0: 
                    res_list.append([nums[i], nums[l], nums[r]]) 
                    l += 1  # 右移一位 
                    r -= 1  # 左移一位 
                    while l < r and nums[l] == nums[l - 1]: 
                        # 從左往右，相同數值直接跳過 
                        l += 1 
                    while r > l and nums[r] == nums[r + 1]: 
                        # 從右往左，相同數值直接跳過 
                        r -= 1 
                elif three_sum > 0: 
                    # 大于零，右邊數值大，左移 
                    r -= 1 
                else: 
                    # 小于零，左邊數值小，右移 
                    l += 1 
    return res_list 

在四種二分變種中，根據王爭算法專欄中，寫死low = 0，high = len(list) - 1。循環條件low <= high。往左移動high = mid - 1，往右移動low = mid + 1

def binary_search(nums, target): 
 '''標準二分算法模板''' 
    low = 0 
    high = len(nums) - 1  # 注意1 low和high用于跟蹤在其中查找的列表部分 
    while low <= high:  # 注意2 只要還沒有縮小到只有一個元素，就不停的檢查 
        mid = (low + high) // 2 
        if list[mid] == target: 
            return mid 
        elif list[mid] > target: 
            high = mid - 1  # 注意3 猜的數字大了 
        elif list[mid] < target: 
            low = mid + 1   # 注意4 猜的數字小了 
    return mid 
 
 
def bsearch_low(nums,target): 
    '''求第一個等于定值 ''' 
    low = 0 
    high = len(nums) - 1 
    # 這里需要 <= 
    while low <= high: 
        # 這里需要注意： 就是使用((high - low) >> 1)需要雙擴號 
        mid = low + ((high - low) >> 1) 
        if nums[mid] < target: 
            low = mid + 1 
        elif nums[mid] > target: 
            high = mid - 1 
        else: 
            if mid == 0 or nums[mid-1] != target: 
                return mid 
            else: 
                high = mid -1 
 
    return -1 
 
def bsearch_high(nums,target): 
    '''求最后一個等于定值的''' 
    low = 0 
    higt = len(nums) -1 
    while low <= higt: 
        mid = low + ((higt- low) >>1 ) 
        if nums[mid] > target: 
            higt = mid - 1 
        elif nums[mid] < target: 
            low = mid +1 
        else: 
            if mid == (len(nums) -1) or nums[mid] != nums[mid+1]: 
                return mid 
            else: 
                low = mid +1 
    return  -1 
 
''' 
查找第一個大于等于給定值的元素 
* 如序列：3，4，6，7，19 查找第一個大于5的元素，即為6，return 2 
* 第一個大于給定值，則說明上一個小于給定值，依次判斷 
''' 
def bsearch_low_not_less(nums,target): 
    low = 0 
    high = len(nums) -1 
    while(low<=high): 
        mid = low + ((high-low) >>1) 
        if nums[mid] >= target: 
            if mid == 0 or nums[mid - 1] < target: 
                return mid 
            else: 
                # 往左移動 
                high = mid - 1 
        else: 
            # 往右移動 
            low = mid +1 
    return -1 
 
''' 
查找第一個小于給定值的元素 
* 如序列：3，4，6，7，19 查找第一個小于5的元素，即為4，返回1 
* 第一個大于給定值，則說明上一個小于給定值，依次判斷 
''' 
def bsearch_high_not_greater(nums,target): 
    '''求最后一個小于等于值''' 
    low = 0 
    higt = len(nums) -1 
    while low <= higt: 
        mid = low + (( higt -low ) >> 1) 
        if nums[mid] <= target: 
            if (mid == len(nums) -1) or (nums[mid + 1] > target): 
                return mid 
            else: 
                low = mid +1 
        else: 
            higt = mid -1 
    return  -1 

滑動窗口

原文：https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA

滑動窗口算法是雙指針技巧的最高境界，主要用于兩個字符串匹配的問題。

掌握了滑動窗口的解題模板可以輕松解決一系列字符串匹配的問題。

下面模板代碼來源labuladong，解決LeetCode 76 題，Minimum Window Substring，求最小覆蓋子串。

/* 滑動窗口算法框架 */ 
string minWindow(string s, string t) { 
     // 兩個unordered_map ，一個need記錄模式串的字符數量，一個window記錄窗口的字符 
    unordered_map<char, int> need, window; 
    // 初始化need 
    for (char c : t) need[c]++; 
 
    int left = 0, right = 0; 
    // 兩個unordered_map的符合條件數目 
    int valid = 0; 
    // 記錄最小覆蓋子串的起始索引及長度 
    int start = 0, len = INT_MAX; 
    while (right < s.size()) { 
        // c 是將移入窗口的字符 
        char c = s[right]; 
        // 右移窗口 
        right++; 
        // 進行窗口內數據的一系列更新 
        if (need.count(c)) { 
            window[c]++; 
            if (window[c] == need[c]) 
                valid++; 
        } 
 
        // 判斷左側窗口是否要收縮 
        while (valid == need.size()) { 
            // 在這里更新最小覆蓋子串 
            if (right - left < len) { 
                start = left; 
                len = right - left; 
            } 
            // d 是將移出窗口的字符 
            char d = s[left]; 
            // 左移窗口 
            left++; 
            // 進行窗口內數據的一系列更新 
            if (need.count(d)) { 
                if (window[d] == need[d]) 
                    valid--; 
                window[d]--; 
            }                     
        } 
    } 
    // 返回最小覆蓋子串 
    return len == INT_MAX ? 
        "" : s.substr(start, len); 
} 

在python里unodered map可以用collections.defaultdict和collections.Counter實現