C++ O(n) using HashMap, beating 89% with comments


  • 0
    J
    int maxSubArrayLen(vector<int>& nums, int k) {
            unordered_map<int,int>  hash;   // for a given value, store the first i, where 0~i sums to certain value
            int sum = 0, n = nums.size(), longest = 0;
            
            hash[0] = -1;                   // start from beginning of this array
            for(int i = 0; i < n; ++i){
                sum += nums[i];
                // 1. update maxlength
                if(hash.find(sum-k) != hash.end()){ // a start-from-head range sums to (k-sum) before
                    longest = max(longest, i- hash[sum-k]);
                }
                // 2. update hash
                if(hash.find(sum) == hash.end()){
                    hash[sum] = i;
                }
            }
            return longest;
        }
    

Log in to reply
 

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