C++ solution using a hash table and a little trick (90 percentile)


  • 0
    G
    class Solution {
    public:
    
        int findMaxLength(vector<int>& nums) {
            
            vector<int> T(nums.size(),0);
            
            //
            // we'll modify the array such that instead of '0' we'll have '-1'
            //
            
            transform(nums.begin(),nums.end(),T.begin(),[](const int i)->int {if(i == 0) return -1; return 1;});
            
            vector<int> PS(T.size(),0);
            
            //
            // Create a partial Sum array from the transformed array
            //
            
            partial_sum(T.begin(),T.end(),PS.begin());
            
            int Max = 0;
            
            //
            // We'll store sums with their corresponding indexes in the HT below
            //
            
            unordered_map<int,int> M;
            M[0] = -1;
            
            for(int i = 0; i < PS.size(); ++i)
            {
                auto F = M.find(PS[i]);
                
                if(F != M.end())
                {
                    //
                    // We've already seen this Partial Sum before
                    // the length of the subarray is the distance between the current index
                    // and the index of the previous PS.
                    //
                    
                    Max = max(Max,i - F->second);
                }
                else
                {
                    //
                    // if this is the first time we're seeing this PS
                    // we store it with it's index
                    //
                    
                    M[PS[i]] = i;
                }
            }
            
            return (Max);
        }
    };

Log in to reply
 

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