基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/contiguous-array/

資料結構與演算法

• Hash Map

題意

給予一個只有 0 和 1 的陣列，找出一個最長的有相同數量的 1 和 0 的子陣列的「長度」

想法

將 0 視為 -1 ， 1 視為 0 進行加總

• 當和為 0 時是為符合條件 - 因為 0 和 1 的數量相同
• 走訪時邊判斷邊暫存最大長度
• 走訪完成時回傳暫存的最大長度作為結果

提早完成 - Sum 為 0

從位置 [0] 開始加的加總後為 0 ，和暫存的最大比較，若大於則替換。

其他的則如下處理

Hash Map 的用法

• Day 1 - 1. Two Sum - 解法與複雜度 - LeetCode in Swift
• Day 3 - 121. Best Time to Buy and Sell Stock - 解法與複雜度 - LeetCode in Swift

和本系列第一天的 Two Sum 的概念類似，把目標值作為 key ，索引作為 value 。暫存最大值的方式則像是第三天的買賣股票的貪婪。

當目前索引為止元素的加總無法達到所有條件，就可以把這個值加入 hash map 。

map[sum] = index

但是當 map[sum] 已經有值時，為了能確保最大長度，則不覆寫。

計算長度，必要時則更新

而記錄的所以就作為加總為 0 的停止點，陣列右邊的元素的加總和這個數字 相等 的的時候，代表從「停止點」到當前位置 1 和 0 的數量相同。

因此就可以開始計算長度，比暫存長度長的時候就可以更新了。

程式碼

class Solution {
    func findMaxLength(_ nums: [Int]) -> Int {
        var map = [Int:Int]()
        var maxLength = 0
        var sum = 0

        for index in 0..<nums.count {
            let number = nums[index]
            sum = sum + (number == 1 ? 1 : -1)

            if sum == 0 {
                let currentLength = index + 1
                maxLength = max(maxLength, currentLength)
            }

            if let storedIndex = map[sum] {
                let currentLength = index - storedIndex
                maxLength = max(maxLength, currentLength)
            } else {
                map[sum] = index
            }
        }
        return maxLength
    }
}

執行結果

• Runtime: 427 ms (Beats 82.76%)
• Memory: 16.5 MB (Beats 31.3%)

複雜度分析

令 n 為陣列的長度

結語

以上，就是今天的 LeetCode in Swift ，

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！