前言

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

Two Pointer

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

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

1
2
3
4
5
6
7
8
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，如果相同，就繼續檢查下一個字元，直到兩個指標相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 題目：

難度較低

難度較高

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個關鍵步驟的呈現方式

1
2
3
4
5
6
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題目：

Example: Max Consecutive Ones III

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

1
2
3
4
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的數量：

1
2
# CONDITION TO STOP EXPANSION
count == 2:

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

1
2
3
4
5
6
7
8
9
10
11
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。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
2
3
4
5
6
[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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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. 最後，處理邊緣情況

參考