Maximum Number of Non-Overlapping Subarrays with Sum Equals Target (LeetCode 1546)

One user posted online that a company rejected a 985‑master candidate because his salary expectation (28k, acceptable at 25k) exceeded the company’s maximum offer, arguing that higher salaries would disrupt team salary balance.

The author counters that salary differences are normal due to varying education, experience, and ability, and that individual compensation should reflect personal merit rather than a team average.

--- Below is today’s algorithm problem ---

The problem is LeetCode 1546: “Maximum Number of Non‑Overlapping Subarrays with Sum Equals Target”, difficulty medium.

Given an integer array nums and an integer target , return the maximum number of non‑empty, non‑overlapping subarrays such that each subarray’s sum equals target .

Example 1: Input: nums = [1,1,1,1,1], target = 2 → Output: 2 . Explanation: Two non‑overlapping subarrays [1,1] and [1,1] sum to 2.

Example 2: Input: nums = [-1,3,5,1,4,2,-9], target = 6 → Output: 2 . Explanation: Three subarrays sum to 6 – [5,1] , [4,2] , [3,5,1,4,2,-9] – but only the first two are non‑overlapping.

Constraints:

1 ≤ nums.length ≤ 10⁵

-10⁴ ≤ nums[i] ≤ 10⁴

0 ≤ target ≤ 10⁶

Problem Analysis

The task is to find the maximum count of subarrays whose sum equals target . We can use a prefix‑sum map to detect subarrays with the required sum; a sliding‑window approach fails because the array may contain negative numbers.

After locating a qualifying subarray via prefix sums, we must record its ending index because subsequent subarrays must start after the previous subarray’s end to avoid overlap.

Note that the condition start >= last uses “≥” because start represents the open‑interval start (the next element after the actual start).

Java Solution

public int maxNonOverlapping(int[] nums, int target) {
    int ans = 0, last = -1, preSum = 0;
    Map
mp = new HashMap<>();
    mp.put(0, -1);
    for (int i = 0; i < nums.length; i++) {
        preSum += nums[i];
        Integer start = mp.get(preSum - target);
        // start is the open‑interval start index
        if (start != null && start >= last) {
            ans++;
            last = i; // closed‑interval end index
        }
        mp.put(preSum, i);
    }
    return ans;
}

C++ Solution

int maxNonOverlapping(vector
& nums, int target) {
    int ans = 0, last = -1, preSum = 0;
    unordered_map
mp;
    mp[0] = -1;
    for (int i = 0; i < nums.size(); i++) {
        preSum += nums[i];
        auto it = mp.find(preSum - target);
        // it->second is the open‑interval start index
        if (it != mp.end() && it->second >= last) {
            ++ans;
            last = i; // closed‑interval end index
        }
        mp[preSum] = i;
    }
    return ans;
}