# [Prefix-Sum]
# https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
# 325. Maximum Size Subarray Sum Equals k

# History:
# Facebook
# 1.
# Dec 14, 2019
# 2.
# Apr 11, 2020

# Given an array nums and a target value k, find the maximum length of a subarray that sums to k.
# If there isn't one, return 0 instead.
#
# Note:
# The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
#
# Example 1:
#
# Input: nums = [1, -1, 5, -2, 3], k = 3
# Output: 4
# Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
# Example 2:
#
# Input: nums = [-2, -1, 2, 1], k = 1
# Output: 2
# Explanation: The subarray [-1, 2] sums to 1 and is the longest.
# Follow Up:
# Can you do it in O(n) time?


class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        pre_see = {0: -1}

        prefix_sum = 0
        ret = 0

        for i, n in enumerate(nums):
            prefix_sum += n

            if prefix_sum - k in pre_see:
                ret = max(ret, i - pre_see[prefix_sum - k])

            if prefix_sum not in pre_see:
                pre_see[prefix_sum] = i

        return ret
