Python super simple O(n) time complexity


  • 0
    A

    save summing value from pos 0 to i in hashtable as htab[val] = pos.
    for each new i, check do we have val-k in hashtable. If yes, save the max length.

    class Solution(object):
        def maxSubArrayLen(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            
            htab = {0:0}
            maxlen = 0
            val = 0
    
            for i in range(len(nums)):
                val += nums[i]
                maxlen = max(maxlen, i+1-htab.get(val-k,i+1))
                htab[val] = min(htab.get(val,len(nums)),i+1)
    
            return maxlen
    
    

Log in to reply
 

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