525. Contiguous Array

題目理解

題目連結：525. Contiguous Array

題目要求我們在一個二進制數組中找到長度最長的連續子數組，該子數組內的0和1的數量相等，我們需要找到包含相等數量的0和1的最長連續子數組的長度

範例

1. 輸入: [0, 1] 輸出: 2 解釋: [0, 1] 是一個包含相等數量0和1的最長子數組。
2. 輸入: [0, 1, 0] 輸出: 2 解釋: [0, 1] (或 [1, 0]) 是一個包含相等數量0和1的最長子數組。

限制條件

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1

解題思路

為了解決這個問題，我們可以將0視為-1，這樣問題就轉化為在數組中找到和為0的最長子陣列

解題步驟

1. 使用一個 hash table 來存儲前綴和及其對應的索引。前綴和是指從數組開始到當前元素的累積和。
2. 遍歷數組，對於每一個元素，更新當前的前綴和。如果這個前綴和已經出現過，則說明在這兩個索引之間的子數組的和為0，此時更新最長子數組的長度
3. 如果當前的前綴和不在hash table中，則將其存入

詳細步驟

1. 初始化 hash table diff，並將diff[0]設置為-1，表示在開始前前綴和為0
2. 遍歷數組，對於每個元素：
   • 如果是1，則將sum加1；如果是0，則將sum減1
   • 如果當前的sum已經在hash table中出現過，則計算當前索引與hash table中該sum對應索引的差，更新最長子數組長度
   • 如果當前的sum不在 hash table 中，則將其和當前索引存入

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;
    }
};

• 時間複雜度: O(n)
• 空間複雜度: O(n)

---

Alternative by @kevinptt0323

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);
    }
}