325. Maximum Size Subarray Sum Equals k (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # O(n) hash
        h = {0: 0}
        result = 0
        nums = [0] + nums
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
            if nums[i] not in h:
                h[nums[i]] = i
            if nums[i] - k in h:
                result = max(result, i - h[nums[i] - k])
        return result
        
        # O(n^2) TLE
        for i in range(len(nums) - 1):
            nums[i + 1] += nums[i]
        nums = [0] + nums
        n = len(nums)
        for i in range(n - 1, -1, -1):
            for j in range(n - i):
                if nums[j + i] - nums[j] == k:
                    return i
        return 0