Leetcode 0325. Maximum Size Subarray Sum Equals k

Problem statement

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

Solution

Evaluate cumulative sums and put them into hash table as keys and as values use indexes: actually we need to keep only the smallest and the biggest indexes. Then for each number $s$ in our hash-table we look for number $s+k$ in this hash-table, and if it exists, we find the longest distance in $O(1)$, using $4$ comparisons: for $a_1, a_2$ and $b_1, b_2$ we need to evaluate all $4$ options.

Complexity

Time complexity is $O(n)$ as well as memory.

Code

class Solution:
    def maxSubArrayLen(self, nums, k):
        cumsum = [0] + list(accumulate(nums))
        dic_max = {c:i for i,c in enumerate(cumsum)}
        dic_min = {c:len(nums) - i for i,c in enumerate(cumsum[::-1])}

        ans = 0
       
        for num in dic_min:
            if num + k in dic_min:
                a, b = dic_min[num], dic_max[num]
                c, d = dic_min[num + k], dic_max[num + k]
                ans = max(ans, d-a, d-b, c-a, c-b)
                
        return ans