525. Contiguous Array

題目連結：525. Contiguous Array

題目描述

給定一個二元陣列 nums，請找出長度最長的連續子陣列，使得該子陣列內的 0 和 1 的數量相等，並返回該子陣列的長度。

範例

1. 輸入：[0, 1]
   輸出：2
   解釋：整個陣列 [0, 1] 包含相等數量的 0 和 1。
2. 輸入：[0, 1, 0]
   輸出：2
   解釋：最長的連續子陣列是 [0, 1] 或 [1, 0]，它們都包含相等數量的 0 和 1。

限制條件

• 1 <= nums.length <= 10^5
• nums[i] 為 0 或 1

解題思路

此題要求我們找出二元陣列中包含相等數量的 0 和 1 的最長連續子陣列。為了達到線性時間複雜度，我們需要找到一種有效的方法。

轉換問題

我們可以將問題轉換為在陣列中找到總和為 0 的最長連續子陣列。具體步驟如下：

1. 將 0 視為 -1：將陣列中的所有 0 替換為 -1。這樣，問題就轉化為在陣列中找到總和為 0 的最長連續子陣列。
2. 使用前綴和與雜湊表：
   • 前綴和：計算陣列的前綴和，sum[i] 表示從第 0 個元素到第 i 個元素的累計和。
   • 雜湊表（哈希表）：使用一個雜湊表來記錄每個前綴和第一次出現的索引位置。
3. 找到總和為 0 的子陣列：
   • 當兩個位置的前綴和相同時，表示在這兩個位置之間的子陣列總和為 0。
   • 我們可以計算這些子陣列的長度，並更新最長的長度。

詳細步驟

1. 初始化：
   • 建立一個雜湊表 diff，鍵為前綴和，值為該前綴和首次出現的索引。
   • 將 diff[0] = -1，表示在開始之前，累計和為 0。
2. 遍歷陣列：
   • 初始化 sum = 0，ans = 0。
   • 對於每個元素 nums[i]：
     • 如果 nums[i] == 1，則 sum += 1。
     • 如果 nums[i] == 0，則 sum += -1。
     • 檢查 sum 是否已在雜湊表中：
       • 已存在：表示在之前某個位置 diff[sum]，累計和與當前相同，更新最長長度 ans = max(ans, i - diff[sum])。
       • 不存在：將當前的 sum 與索引 i 存入雜湊表 diff。
3. 返回結果：
   • 遍歷結束後，返回最長的長度 ans。

程式碼

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        const int n = nums.size();
        unordered_map<int, int> diff;
        diff[0] = -1;

        int sum = 0;
        int ans = 0;
        for (int i = 0; i < n; i += 1) {
            sum += (nums[i] == 1 ? 1 : -1);
            if (diff.count(sum)) {
                ans = max(ans, i - diff[sum]);
            } else {
                diff[sum] = i;
            }
        }

        return ans;
    }
};

優化版本

使用 C++17 的 try_emplace 可以稍微優化查找和插入的效率：

for (int i = 0; i < n; i += 1) {
    sum += (nums[i] == 1 ? 1 : -1);
    const auto& [itr, success] = diff.try_emplace(sum, i);
    if (!success) {
        ans = max(ans, i - itr->second);
    }
}

時間與空間複雜度分析

時間複雜度：O(n)

• 遍歷陣列：我們只需要遍歷一次陣列，時間為 O(n)。
• 雜湊表操作：在 C++ 中，unordered_map 的查找和插入操作平均時間為 O(1)。
• 總計：因此，總的時間複雜度為 O(n)。

空間複雜度：O(n)

• 雜湊表：最壞情況下，累計和在每個位置都是不同的，雜湊表需要存儲 n 個鍵值對。
• 總計：因此，空間複雜度為 O(n)。