Max Size Subarray Sum Equals K

题目描述

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.

Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2: Given nums = [-2, -1, 2, 1], k = 1, return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

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

解题方法

Solution

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)
        sums = [0 for i in range(length+1)]
        sum_map = {}
        sums[0] = 0
        sum_map[0] = [0]
        max_length = -sys.maxint

        for i in range(1, length+1):
            sums[i] = sums[i-1] + nums[i-1]
            if sums[i] in sum_map:
                sum_map[sums[i]].append(i)
            else:
                sum_map[sums[i]] = [i]

        for i in range(length, -1, -1):
            sum_i = sums[i]
            if (sums[i] - k) in sum_map:
                idx_list = sum_map[sums[i]-k]
                for idx in idx_list:
                    if i > idx and i - idx > max_length:
                        max_length = i - idx

        if max_length == -sys.maxint:
            return 0
        else:
            return max_length

Reference