[Leetcode Pattern] Sliding Window

Pattern 精髓

所謂 window 就是指一個範圍，例如字串 or Array 裡的區間，而 Sliding 就是只可以動態調整 window 大小，Sliding window 最主要是避免重複計算

幾個構成的條件

• 透過操作 2 個 point 構成 window ，計算來達成目的
• window 的搜索範圍是一串連續的資料

例題帶入講解

最經典的就是 leetcode 的 209. Minimum Size Subarray Sum

題目是要我們找到一個 Array 例如 [2,3,1,2,4,3] 裡面最少的 subarray 且 subarray 的 sum要大於等於 target ，假設 target = 7 即 subarray 為 [4, 3] 時滿足條件，所以 return subarray 的 count 2

首先看一下暴力解：

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var ans = Int.max
        for i in 0..<nums.count {
            print("<i start:\(i)>")
            for j in i..<nums.count {
                var sum = 0
                for k in i...j {
                    print("sum += \(nums[k])")
                    sum += nums[k]
                }
                if sum >= target {
                    ans = min(ans, (j - i + 1))
                    break
                }
                print("")
            }
        }
        return ans == Int.max ? -1 : ans
    }
}

▼ 從 log 可以看到

// minSubArrayLen(7,  [2,3,1,2,4,3])

<i start:0>      
sum += 2

sum += 2
sum += 3

sum += 2
sum += 3
sum += 1

sum += 2
sum += 3
sum += 1
sum += 2
...                

可以看到一個現象，每一次要計算 sum 都會把前面已經算得再算一次

例如 2+3 在 2+3+1 時已經算過了，就不用再算一次

▼ 使用 Sliding Widnow 技巧的程式碼:

class Solution {
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        var left = 0
        var subsum = 0
        var ans = Int.max
        for (right, _) in nums.enumerated() {                    
            subsum += nums[right]
            print("sum += \(nums[right])")            
            while subsum >= target && left <= right {
                print("sum -= \(nums[left]) (sum >= target(\(target)))")
                ans = min(ans,(right - left + 1))
                subsum -= nums[left]
                left += 1
            }
            print("")
        }
        return ans == Int.max ? -1 : ans
    }
}

// minSubArrayLen(7,  [2,3,1,2,4,3])

sum += 2

sum += 3

sum += 1

sum += 2
sum -= 2 (sum >= target(7))

sum += 4
sum -= 3 (sum >= target(7))
sum -= 1 (sum >= target(7))

sum += 3
sum -= 2 (sum >= target(7))
sum -= 4 (sum >= target(7))

由 log 可以明顯看出，一開始加 2 + 3 + 1 + 2 之後判斷大於 target 7 ，開始操作 slide window 的 left 跟 right 指摽來控制 sum

▼ 下圖可以清楚看出 2 + 3 + 1 + 2 之後的 steps 如何移動 window