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 sumcurr_sum = 0for num in nums:# add the current number to form current prefix sumcurr_sum += num# calculate the remain of the previous prefix sum for the current sum to be validremain = 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 += 1prev_sum = {
    0:1}curr_sum = 0# otherwise, add the current sum to the prev_sum dictelse:prev_sum[curr_sum] = 1return ans

二刷

两个关键：

1. 使用prefix肯定是需要的
2. 如何快速使用prefix的结果，这边的不同在于结果不可以有overlap。所以在遍历到每个位置的时候我们只需要保存一部分的prefix sum，而无需之前所有的prefix sum。所以就可以用不同的形式来储存这个prefix sum

class Solution {
    
public:int maxNonOverlapping(vector<int>& nums, int target) {
    unordered_set<int> seen;seen.insert(0);int res = 0;int curr_sum = 0;for(auto& num : nums){
    curr_sum += num;if(seen.count(curr_sum-target)){
    res++;curr_sum = 0;seen = {
    0};}else{
    seen.insert(curr_sum);}}return res;}
};