題目： LeetCode - 525. Contiguous Array

題目說明

給一個陣列，找出一段裡面 0 和 1 個數相等的最長子陣列。

解題思路

定義一個 target，當每次訪問 nums 的元素時，若元素為 1 則 + 1，若為 0 則 - 1，並查詢這個 target 是否出現過，若有則代表這一段子陣列裡面的 0 和 1 的個數相等。使用 unordered_map<int, int> 存放資料，key 為 target，value 為該 target 的 index。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int target = 0, maxLength = 0, n = nums.size();
        unordered_map<int, int> map;
        map.insert({0, -1});
        for(int i = 0; i < n; ++i)
        {
            target += (nums[i] == 0) ? -1 : 1;
            if(map.count(target))
                maxLength = max(maxLength, i - map[target]);
            else
                map[target] = i;
        }
        return maxLength;
    }
};