C++ O(n) Solution


  • 2
    Y
    class Solution {
    public:
        int maxSubArrayLen(vector<int>& nums, int k) {
            int n = nums.size();
            if (n == 0) return 0;
            
            unordered_map<int, int> m;
            m[0] = -1;
            
            int sum = 0, maxLen = 0;
            for (int i = 0; i < n; i++) {
                sum += nums[i];
                if (m.find(sum - k) != m.end())
                    maxLen = max(maxLen, i - m[sum - k]);
                if (m.find(sum) == m.end())
                    m[sum] = i;
            }
            
            return maxLen;
        }
    };
    

Log in to reply
 

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