Simple C++ O(n) solution using hash table


  • 1
    A

    Traverse the array from front to end, let a variable cur increase by 1 if we encounter 1, decrease by 1 if we encounter 0. Use an hash table (unordered_map in C++) to record the first index for each values of cur. In each iteration, we look up the hash table for the first index at which cur has the same value. Output the maximum index difference.

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.