Leetcode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target (python)

题目

解法：prefix+hashmap+greedy

参考leetcode给的两条hint：

• Keep track of prefix sums to quickly look up what subarray that sums “target” can be formed at each step of scanning the input array.

• It can be proved that greedily forming valid subarrays as soon as one is found is optimal.

  详细解释见代码注释

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # dict store the previously appeared prefix sum. Reset it if we find a valid subarray. Note that we need to store the prefix sum so that we don't need to do sum over and over again
        # why using dict. Because at a new position, we have to look back to see if any previous position and current position can form a valid sequence. By store the prefix sum in a dict, we can look up if it is possible for O(1)
        prev_sum = {0:1}
        ans = 0
        # the ruuning current sum
        curr_sum = 0
        
        for num in nums:
            # add the current number to form current prefix sum
            curr_sum += num
            # calculate the remain of the previous prefix sum for the current sum to be valid
            remain = curr_sum-target
            # if the remain has appeared in the previously appeared prefix sum, meaning there is a valid subarray appeared between the current prefix_sum position and the remain prefix sum position. 
            # Increment the count by 1 and reset the prev_sum dict. also reset curr_sum to 0.
            # Why reseting, because we are forming the valid subarray greedly. Once valid subarray is found at current position, all the numbers before that position does not matter any more. 
            if remain in prev_sum:
                ans += 1
                prev_sum = {0:1}
                curr_sum = 0
            # otherwise, add the current sum to the prev_sum dict
            else:
                prev_sum[curr_sum] = 1
        
        return ans