LC-1546 Medium LeetCode

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 48% Topics: Array, Hash Table, Greedy, Prefix Sum

Reading material

Arrays & Hashing 12 min Greedy 11 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def maxNonOverlapping(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lookup = {0:-1}
        result, accu, right = 0, 0, -1
        for i, num in enumerate(nums):
            accu += num
            if accu-target in lookup and lookup[accu-target] >= right:
                right = i
                result += 1  # greedy
            lookup[accu] = i
        return result

Solution from kamyu104/LeetCode-Solutions · MIT