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

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

Leetcode Solutions

Prefix Sum with Hash Map

  1. Initialize a hash map to store the cumulative sum and its corresponding index, and set the initial sum to 0 with index -1.
  2. Initialize variables for the cumulative sum, the count of non-overlapping subarrays, and the last index of the previous subarray found.
  3. Iterate through the array, updating the cumulative sum at each step.
  4. Check if the cumulative sum minus the target is in the hash map.
  5. If it is, and the last index of the previous subarray is less than or equal to the index stored in the hash map, increment the count and update the last index to the current index.
  6. Update the hash map with the current cumulative sum and index.
  7. Return the count of non-overlapping subarrays.
UML Thumbnail

Greedy Approach with Single Pass

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...