LeetCode 課前預習 - 掌握 Two Pointer 和 Sliding Window 捕捉使用時機

前言

今天想要深度的去了解Two pointer與sliding window 的使用，這也是面試常見的技巧。主要整理出『如何辨識要使用這些技巧』。

Two Pointer

那我們先從two pointer開始，因為sliding window其實是two pointer的一種特例，或是進階應用。

那麼什麼是two pinter呢？pinter 俗稱指標，指標用來儲存另一個物件的記憶體位置，通常在leetcode中，指標只是一個整數，用來指向陣列的某個物件索引。

pointer = 0
arr = [10, 30, 50, 70, 100]
       ^
arr[pointer] = arr[0] = 10
pointer = 3
arr = [10, 30, 50, 70, 100]
                    ^
arr[pointer] = arr[3] = 70

Two pointer就是指向陣列的兩個指標，通常是指向陣列的頭尾，然後向中間移動，或是指向陣列的兩個不同位置，然後向中間移動。雙指標允許我們同時查看兩個不同的值，然後我們根據這兩個值的關係來決定下一步的操作。

Example: Valid Palidorme

Palidorme 就是一個經典的 two pointer 例子，Palidorme 又稱作『回文』，向前讀和向後讀是一樣的，例如："racecar"(倒過來也長一樣)。為了開始檢查，我們在兩端初始化一個指標，left和right，分別指向字串的開頭和結尾。然後我們每次檢查兩個指標指向的字元是否相同，如果不同，就返回False，如果相同，就繼續檢查下一個字元，直到兩個指標相遇。

string = 'racecar'
          l     r
left = 0     
right = 6     
string[left] = 'r'
string[right] = 'r'
'r' == 'r'
# The letters are equal, decision -> bring left and right closer.
string = 'racecar'
           l   r
left = 1    
right = 5
string[left] = 'a'
string[right] = 'a'
'a' == 'a'
# The letters are equal, decision -> bring left and right closer.
string = 'racecar'
            l r
left = 2   
right = 4
string[left] = 'c'
string[right] = 'c'
'c' == 'c'
# The letters are equal, decision -> bring left and right closer.
string = 'racecar'
             l 
             r
left = 3
right = 3
string[left] = 'c'
string[right] = 'c'
'c' == 'c'

以下是python代碼

def is_palindrome(string):
    # Initialize pointers
    left = 0 
    right = len(string) - 1
    # Check all letters in the string 
    while left < right:
        # If letters are not equal
        # Decision -> Return False
        if string[left] != string[right]:
            return False  
        # Else, the letters are equal
        # Decision -> Bring left and right closer and compare again
        else:
            left += 1        
            right -= 1
    return True   

Other Scenarios

two pinter通常不像是上面的例子這麼簡單，有時候需要發揮想像力。以下是常見使用two pointer的情境：

1. Binary Search 二元搜尋
2. Slow and Fast Pointer to detect a cycle
3. One pointer as a boundary and one another to search
4. Pointer at the beginning of two sorted arrays
5. Sliding Window (Advanced)

Leetcode 題目：

難度較低

• Valid Palindrome
• Two Sum Sorted
• Remove Duplicates from Sorted Array
• Merged Two Sorted Arrays
• Intersection of Two Arrays II
• Binary Search
• Reverse a String

難度較高

• Sorted Colors
• Container with Most Water
• Sliding Window
• Binary Search Rotated Array

How to Recognize it

我們可以通過幾種方式來辨識two pointer的使用時機：

1. O(N^2)降低成O(N)：把雙層for迴圈的循環減少到單層迴圈
2. Input是有序的：如果input已經排序或是有順序
3. 兩個索引的比較：如果我們要將一個索引值跟另一個索引值進行比較
4. 兩個索引的交換：我們需要在索引之間交換
5. 陣列的分區：如果我們需要將陣列分區，然後在分區中進行操作

Sliding Window

Sliding window 是雙指標的擴展，透過left和right兩個指標來建立window（窗口），通常問題是要我們反回滿足特定條件的最大或最小子範圍。因此我們透過滑動（收縮和擴展）『window』來找到最佳範圍。在這裡我們會使用Max Consecutive Ones III來舉例。

Key Steps

但是在開始之前，我們要先知道Sliding Window的三個關鍵步驟：

1. Expand out Window 擴展窗口
2. Meet the condition and process the window 滿足條件並處理窗口
3. Shrink the window 收縮窗口

以下是代碼中3個關鍵步驟的呈現方式

def sliding_window(nums):
    # Iterate over elements in our input
        # Expand the window
        # Meet the condition to stop expansion
            # Process the current window   
            # Contract the window

Other Scenarios

Leetcode 常見的Sliding Window題目：

• Max Consecutive Ones I
• Max Consecutive Ones II
• Max Consecutive Ones III
• Longest Substring with At Most K Distinct Characters
• Longest Substring Without Repeating Characters
• Minimum Window Substring

Example: Max Consecutive Ones III

問題如下，我們可以替換1次0，找到最大的連續1的數量。但其實題目可以換句話說：我們要找到最大的window，裡面最多只有1個0。

MAX CONSECUTIVE ONES II 
Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
Input: [1,0,1,1,0]
Output: 4

那麼，促使我們停止擴大window的條件是什麼呢？
就是當我們的window中0的數量超過1個時，我們就要停止擴大window。因為 0 太多拉！再擴大下去，會遠遠的超過偏差。換句話說我們需要擴展window，直到我們的window中0的數量超過1個，要停下腳步思考一下。

我們可以使用一個變數count來記錄0的數量：

# CONDITION TO STOP EXPANSION
count == 2:

那我們重新把這個停止擴大的條件放入我們的sliding window結構

def sliding_window(nums):
    left, right = 0, 0          # Intialize our window's bound
    count = 0                   # Track how many 0’s are in the window
    # Iterate over elements in our input
    while right < len(nums):
        # Expand the window
        # Meet the condition to stop expansion
        while count > 1:
            # Process the current window   
            # Contract the window
        right += 1  

因此，我們透過向右擴展window，直到我們的window中0的數量超過1個，我們就要停止擴展window。但是等等！我們怎麼知道count什麼時候會被增加呢？我們需要在擴展window的時候，檢查我們的window中是否有0，如果有，我們就要增加count。

# 向右擴展window時要檢查是否有0
if nums[right] == 0:
    count += 1

那我們再把它加進去代碼中

def sliding_window(nums):
left, right = 0, 0          # Intialize our window's bound
count = 0                   # Track how many 0’s are in the window
# Iterate over elements in our input
while right < len(nums):
    # Expand the window 
    if nums[right] == 0:        
        count += 1
    # Meet the condition to stop expansion
    while count > 1:
        # Process the current window
        # Contract the window
    right += 1

很好！現在我們已經擴展了視窗，直到滿足條件為止。那我們接下來要做什麼呢？就是開始尋找我們的最佳解，在這個題目就是找到最大長度的連續1，我們可以透過global_max來記錄最大的連續1的長度。一但發現更好的解，我們就要更新global_max。在最後作為結果返回。當我們已經檢查過當前的window是否最長後，我們透過增加left來縮小window，直到我們的window中0的數量小於等於1個。

但是要注意的是，當我們增加left之前，也要檢查left是否會讓我們0的數量遞減，因為已經不再window中了，我們要減少count。

def sliding_window(nums):
    left, right = 0, 0          # Our window bounds
    count = 0                   # Track how many 0’s are in the window
    global_max = 0              # Track the maximum, overall
    # Iterate over elements in our input
    while right < len(nums):
        # Expand the window 
        if nums[right] == 0:        
            count += 1
        # Meet the condition to stop expansion
        while count > 1:
            # Process the current window
            global_max = max(global_max, right - left)
            # Contract the window
            if nums[left] == 0:
                count -= 1
            left += 1
        right += 1
   return global_max

作為最後步驟，我們需要處理邊緣情況，就是最大陣列其實是陣列的尾端。

[1, 0, 0, 1, 1, 1, 1, 1]
       l                 r
We never process the current window above because count_of_zeroes never has a chance to equal 2. 
So do this check at the end:
if count_of_zeroes < 2:
    global_max = max(global_max, right-left)

那我們把邊緣狀況加入我們的代碼中：

def sliding_window(nums):
    left, right = 0, 0        # Our window bounds
    count = 0                 # Track how many 0’s are in the window
    global_max = 0            # Track the maximum, overall
    # Iterate over elements in our input
    while right < len(nums):
        # Expand the window 
        if nums[right] == 0:        
            count += 1
        # Meet the condition to stop expansion
        while count > 1:
        # Process the current window
            global_max = max(global_max, right - left)
        # Contract the window
            if nums[left] == 0:
                count -= 1
            left += 1
        right += 1
    if count < 2:
        global_max = max(global_max, right-left)
    return global_max

How to Recognize it

總結來說 Sliding Window 就是需要定義出以下狀況：

1. 何時停止擴展？
2. 處理當前window的時機？
3. 何時收縮window？

因此我們需要3個變數

1. window bounds: 通常是 left, right 來表示window的邊界
2. Track condition: 通常是一個變數來追蹤滿足條件，這個例子裡面我們使用count
3. Return value: 通常是一個變數來記錄最終結果，這個例子裡面我們使用global_max

我們的思考邏輯是這樣的：

1. 定義條件以停止擴展
2. 展開視窗直到滿足條件，但是在展開視窗前，要在right處檢查或處理元素
3. 如果滿足停止擴展的條件，則處理當前視窗
4. 縮小視窗，直到滿足條件，但是在縮小視窗前，要在left處檢查或處理元素
5. 最後，處理邊緣情況

參考

• Medium | Leetcode is Easy! The Two Pointer Pattern.
• Medium | Leetcode is Easy! The Sliding Window Pattern.
• Medium | Leetcode Pattern 2 | Sliding Windows for Strings