Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums tok. If there isn't one, return 0 instead.

Note: The sum of the entirenumsarray is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Givennums=[1, -1, 5, -2, 3],k=3, return4. (because the subarray[1, -1, 5, -2]sums to 3 and is the longest)

Example 2:

Givennums=[-2, -1, 2, 1],k=1, return2. (because the subarray[-1, 2]sums to 1 and is the longest)

Follow Up: Can you do it in O(n) time?

解析

O(n)

The HashMap stores the sum of all elements before index i as key, and i as value. For each i, check not only the current sum but also (currentSum - previousSum) to see if there is any that equals k, and update max length.

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = 0
        hashmap = {}
        sumValue = 0
        for i in xrange(len(nums)):
            sumValue += nums[i]
            # 先判断从0到i的和是否等于k，因为从0到i的长度一定大于0到i中的一个subarray
            if sumValue == k:
                # 不能直接return，因为后边的subarray可能更长
                result = i + 1
            elif sumValue - k in hashmap:
                result = max(result, i - hashmap[sumValue-k])
            # 需要判断sumvalue的值是否存在，因为i要尽可能的在左边，确保result尽可能的长，例子[1,0,-1],k=-1,output=1(如果不加if),expected=2
            if sumValue not in hashmap:
                hashmap[sumValue] = i
        return result