Skip to content

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

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int maxNonOverlapping(vector<int>& nums, int target) {
    // Ending the subarray ASAP always has a better result.
    int ans = 0;
    int prefix = 0;
    unordered_set<int> prefixes{0};

    // Greedily find the subarrays that equal to the target.
    for (const int num : nums) {
      // Check if there is a subarray ends in here and equals to the target.
      prefix += num;
      if (prefixes.count(prefix - target)) {
        // Find one and discard all the prefixes that have been used.
        ++ans;
        prefix = 0;
        prefixes = {0};
      } else {
        prefixes.insert(prefix);
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public static int maxNonOverlapping(int[] nums, int target) {
    // Ending the subarray ASAP always has a better result.
    int ans = 0;
    int prefix = 0;
    Set<Integer> prefixes = new HashSet<>(Arrays.asList(0));

    // Greedily find the subarrays that equal to the target.
    for (int num : nums) {
      prefix += num;
      // Check if there is a subarray ends in here and equals to the target.
      if (prefixes.contains(prefix - target)) {
        // Find one and discard all the prefixes that have been used.
        ans++;
        prefix = 0;
        prefixes = new HashSet<>(Arrays.asList(0));
      } else {
        prefixes.add(prefix);
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def maxNonOverlapping(self, nums: List[int], target: int) -> int:
    # Ending the subarray ASAP always has a better result.
    ans = 0
    prefix = 0
    prefixes = {0}

    # Greedily find the subarrays that equal to the target.
    for num in nums:
      # Check if there is a subarray ends in here and equals to the target.
      prefix += num
      if prefix - target in prefixes:
        # Find one and discard all the prefixes that have been used.
        ans += 1
        prefix = 0
        prefixes = {0}
      else:
        prefixes.add(prefix)

    return ans