【LeetCode】 525. Contiguous Array

Description

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

給予一個二元陣列，找到最大長度的子陣列，其包含的0和1數量相同。
提示：給予的二元陣列最長不超過50000。

Example:

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.


Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Solution

• 這題蠻難的，想了很久才寫出來，時間還有夠慢XD
• 第一個重點是使用一變數sum，遇到0就減一，遇到1就加一。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ans = 0;
        for(int j = 0; j < nums.size(); j++)
        {
            int sum = 0;
            int count = 0;
            for(int i = j; i < nums.size(); i++)
            {
                if(nums[i] == 0)
                    sum--;
                else if(nums[i] == 1)
                    sum++;

                count++;
                if(sum == 0)
                    ans = ans < count ? count : ans;
            }
        }
        return ans;
    }
};

• 上面是我寫出的第一個版本，就是把所有長度的總和都檢查一次。
  • 複雜度為O(n^2)，吃到TLE。

---

• 改良加速版用了hash的概念，首先計算sum的時候，順便將sum取代掉原數字nums[i]。
  • 假設今天nums為[1, 1, 0, 1, 0]，那麼新的nums就為[1, 2, 1, 2, 1]。
  • 只要兩者數字相同，就代表該區間0和1是一樣多的！
• 因此我們用一個hash儲存每個sum值所在的位置。
  • 如果hash沒有出現過該sum，就將它存入。
  • 如我hash已經出現過了，那就計算長度。
  • 複雜度為O(n)
• 如果還想要更快，必須使用new新增陣列取代掉vector等結構，以縮短allocate的時間。

Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum = 0;
        int ans = 0;
        unordered_map<int,int> hash;
        hash[0] = -1;
        int s = nums.size();
        
        for(int i = 0; i < s; i++)
        {
            if(nums[i] == 0)
                sum--;
            else if(nums[i] == 1)
                sum++;
            
            nums[i] = sum;
            if(hash.count(sum))
                ans = max(ans, i - hash[sum]);
            else
                hash[sum] = i;
        }
        
        return ans;
    }
};

tags: LeetCode C++