###### tags: `LeetCode`,`Pyhon3`,`Medium`
# 525. Contiguous Array
### **題目連結：** [**Contiguous Array**](https://leetcode.com/problems/contiguous-array/description/?envType=daily-question&envId=2024-03-16)

### **解題方向**
* 理解問題：
- 你需要找到含有相等數量的0和1的最長連續子陣列。例如，對於陣列 [0, 1, 0, 1]，最長的子陣列是整個陣列，長度為 4。
* 使用前綴和：
- 你可以將 0 看作是 -1，這樣當一個子陣列的和為 0 時，即表示該子陣列含有相同數量的 0 和 1。遍歷陣列，計算從開始到當前元素的前綴和。
* HashTable的運用：
- 使用一個HashTable來存儲某個前綴和首次出現的索引。HashTable的鍵是前綴和，值是該前綴和對應的索引。如果同一個前綴和在後面的某個點再次出現，這代表從第一次出現該前綴和的索引到當前索引之間的子陣列和為 0（即包含相同數量的 0 和 1）。
* 找出最長的子陣列：
- 每當你遇到一個已經在HashTable中存在的前綴和時，計算當前索引與HashTable中存儲的索引之間的距離。這個距離代表了一個符合條件的子陣列的長度。通過比較所有這樣的距離，你可以找到最長的符合條件的子陣列。
### **完整程式碼**

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # 找出包含相同數量的 0 和 1 的最長連續子陣列
        # 初始HashTable，用於存儲前綴和及其對應的索引。
        sum_index_map = {0: -1}
        max_length = 0
        sum = 0

        # 遍歷數組
        for i, num in enumerate(nums):
            # 更新前綴和。將0視為-1，1保持不變。
            if num == 0:
                sum -= 1
            else:
                sum += 1

            # 檢查當前前綴和是否已經存在於哈希表中
            if sum in sum_index_map:
                # 如果存在，計算當前子數組的長度，並更新最大長度
                max_length = max(max_length, i - sum_index_map[sum])
            else:
                # 如果不存在，將目前前綴和及其索引加入HashTable
                sum_index_map[sum] = i

        return max_length

### **補充說明**
* 初始化：

* 創建一個哈希表 sum_index_map 用來記錄每個前綴和出現的第一個索引。初始時，我們將前綴和 0 的索引設為 -1，表示在開始遍歷任何元素之前，和為0的子數組的「起始位置」在數組開始之前。
* 設置 max_length 為 0，用來跟踪最長子數組的長度。
* sum 也初始化為 0，用來記錄當前的前綴和。
* 遍歷數組：
* 遍歷 nums = [0, 1, 0, 1]。第一個元素是 0，我們將其視為 -1 來更新 sum。所以，sum 變成 -1。因為 -1 沒有在 sum_index_map 中，我們將其加入：sum_index_map[-1] = 0。
* 更新和查詢：
* 接下來，元素是 1，sum 更新為 0（因為 -1 + 1 = 0）。我們在 sum_index_map 中找到了 0，這意味著從索引 -1（即數組開始之前）到索引 1（當前元素的索引）的子數組和為 0，因此0和1的數量相等。這個子數組的長度是 1 - (-1) = 2，更新 max_length 為 2。
* 繼續遍歷，再次遇到 0，sum 變為 -1。在 sum_index_map 中查找 -1，找到了索引 0，意味著從索引 0 到當前索引 2 的子數組和為 0，但這個子數組的長度 2 - 0 = 2 並沒有超過當前的 max_length。
* 最後，又是 1，sum 更新回 0。我們再次在 sum_index_map 中找到了 0，這意味著從索引 -1 到當前索引 3 的子數組和為 0。這個子數組的長度是 3 - (-1) = 4，更新 max_length 為 4。
* 結果：
* 遍歷結束後，我們找到的最長子數組，使得其中0和1的數量相等的長度為 4。