Algorithms & Data Structures : LeetCode 525. Contiguous Array

題目：

Contiguous Array - LeetCode

這一題是最近寫的題目裡，比較有成就感的一題了，因為沒有看解答，就想出自己還算滿意的解。

我的解法：

每次多算一個數時，計算 1 的總和以及 0 的總和，並將其相減得 diff。假如 diff == 0 ， 則可以把這個長度計入計算。假如不是 0 ， 則用 hashMap 記起得此值的 index 。 此後假如有遇到相同的 diff 值，表示在這個區間裡， 0 的個數總和 == 1 的個數總和。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> um;
        int maxVal = 0;
        
        int sum0 = 0;
        int sum1 = 0;
        int diff;
        
        for(int i = 0;i < nums.size();i++) {
            if(nums[i] == 0) {
                sum0++;
            } else {
                sum1++;
            }
            diff = sum0 - sum1;
            
            // 假如重複出現 diff ， 就表示重複的這個區間，0 的個數 == 1 的個數
            if(diff == 0) {
                maxVal = i + 1;
            } else {
                if(um.find(diff) == um.end()) {
                    um[diff] = i;
                } else {
                    maxVal = max(maxVal, i - um[diff]);
                }
            }
        }
        
        return maxVal;
    }
};

TODO :

研究下 LeetCode 的官方解法。