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

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

---

给定一个数组，问数组中最多有多少个不overlap的子数组，它们的和等于target。

常规DP方法，假设dp[i]表示[0,…,i]能找到的最多的子串数目，则对于nums[i+1]，如果从i+1往前，求累加和，如果累加到j的地方，累加和[j,…,i]等于target，则dp[i+1]=dp[j-1]+1。

这种思路的代码如下，需要注意for循环需要满足dp[j]==dp[i]，如果dp[j]<dp[i]，说明j已经回退到上一个累加和等于target的区间，已经有overlap了，需要终止。

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        for(int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            int sum = 0;
            for(int j = i; j > 0 && dp[j] == dp[i]; --j) {
                sum += nums[j - 1];
                if(sum == target) dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
        return dp[n];
    }
};

上述代码的时间复杂度为O(n^2)，在最后几个大数据集上TLE。

参考评论区，用一个hash记录某个前缀和出现的最新下标，对于任意一个数nums[i]，看看prefix_sum-target是否在之前记录的前缀和中（查hash即可），如果在，假设对应下标为j，则说明[j,…,i]之间的累加和等于target，找到一个。不过为了保证不overlap，需要保证下标j不能回退到上一个合法的累加和区间内，每次找到一个合法区间后，用right_most记录其右边界，下次只需要用j和right_most比较大小即可。

完整代码如下：

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash;
        hash[0] = -1;
        int prefix_sum = 0, right_most = -1;
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            prefix_sum += nums[i];
            int supplement = prefix_sum - target;
            if(hash.find(supplement) != hash.end()) {
                int left = hash[supplement];
                if(left >= right_most) {
                    ++ans;
                    right_most = i;
                }
            }
            hash[prefix_sum] = i;
        }
        return ans;
    }
};

本代码提交AC，用时392MS。