325.Maximum Size Subarray Sum Equals k

Tags: [map], [dp], [initialization]

Com: {fb}

Link: https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/#/description

Given an arraynumsand a target valuek, 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:

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

Example 2:

Given nums =[-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?

Solution: DP, Map

class Solution(object):
    def maxSubArrayLen(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)

        left_sum = [0 for _ in xrange(size)]
        left_sum[0] = nums[0]
        for i in xrange(1, size):
            left_sum[i] = left_sum[i - 1] + nums[i]

        # The reason why we put (0 => -1) is like followings:
        # Remember, the key of the left_sum_to_index_map, is the sum of the left part of array.
        # So we think if there is nothing in the array, the left_sum is 0, 
        # in this case the index of the end element of this array is -1.
        # For example, arr = [1, -1, 2, 3, -5, 100, 200, 300], 
        # left_sum[1] = 0, left_sum[4] = 0, but we all know there exist a subarray which has nothing, 
        # and its left_sum also is 0, and its' last element's index we can mark as -1.
        # So we have left_sum[-1] = 0, left_sum[1] = 0, left_sum[4] = 0. 
        # Beause -1 < 1 < 4, so we should put (0=>-1) into the left_sum_to_index_map
        # If k = 100, now we know left_sum[5] = 100, left_sum[prev_i] = left_sum[5] - k = 0.
        # We check left_sum_to_index_map, we find the prev_i = -1, so the start of this subarray is -1 + 1 = 0,
        # so the length of this subarray is 5 - 0 + 1 = 6.
        left_sum_to_index_map = {0: -1}
        max_len = 0
        for i in xrange(size):

            if left_sum[i] not in left_sum_to_index_map:
                # there may exist the duplicate left_sum[i],
                # but here we only record the first i,
                # because, later this i will be prev_index, and we will get a future i,
                # the length of the subarray is (i - (prev_index + 1) - 1), 
                # which means, the prev_index is smaller which is better, so we only record the first i.
                left_sum_to_index_map[left_sum[i]] = i

            # left_sum[i] - left_sum[prev_i] = k
            # left_sum[prev_i] = left_sum[i] - k
            if left_sum[i] - k in left_sum_to_index_map:
                prev_index = left_sum_to_index_map[left_sum[i] - k]
                max_len = max(max_len, i - (prev_index + 1) + 1)

        return max_len

Revelation:

• Thinking process:
• (1) Think I can use DP to get the sum of the subarray in O(1) time complexity.
• (2) I can iterate left, and right pointers by using two level loops, to get all possible subarrays, and to find which sum is equal to k, and which has the max len.
• (3) The sum of the subarray[left: right + 1] = left_sum[right] - left_sum[left - 1], and we want to find sum of the subarray is equal to k. So left_sum[right] - left_sum[left - 1] = k, so we can use map to record left_sum[left - 1], then search it later.
• Pay attention to how do we initialize the left_sum_to_index_map, and the explanation has been commented in code.
• Be aware of that we only need record the first (left_sum[i] => i) in the map, the explanation has been commended in code.

Note:

• Time complexity = O(n), n is the number of elements in the given nums.