C++ O(n) without HashMap


  • 0
    F
    class Solution {
    public:
        int findMaxLength(vector<int>& nums) {
            int n = nums.size();
            vector<int> Idx(2*n+1, -1);
            vector<int> arr(n+1);
            arr[0] = 0;//newhead
            for(int i=1;i<=n;++i){
                arr[i] = arr[i-1] + (nums[i-1]==0?-1:1);
            }
            
            int res = 0;
            for(int i=0;i<=n;++i){
                int m = arr[i]+n;//keep m>=0 as index
                if(Idx[m] == -1){
                    Idx[m] = i;
                }
                else{
                    int len = i - Idx[m];
                    res = max(res, len);
                }
            }
            return res;
        }
    };

Log in to reply
 

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