题目描述

给你一个数组nums和一个整数target。

请你返回非空不重叠子数组的最大数目，且每个子数组中数字和都为target。

示例 1：

输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
示例 2：

输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3：

输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3
示例 4：

输入：nums = [0,0,0], target = 0
输出：3

提示：

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

思路:(dp+前缀和)

• 状态表示：dp[i]表示以i结尾的和为目标值的最大数目不重叠非空子数组数目
• 状态计算: 以是否选择i来划分
• 1.如果i无法与前面的某一个子数组构成一个满足题意得子数组 dp[i] = dp[i-1]
• 2.s[j…i]是一个满足题意的子数组 dp[i] = dp[j-1]+1
• 分析状态表示和状态计算我们发现关键点在于如何快速的判断s[j...i]是否满足题意
• 这里我们通过前缀和来判断 如果s[j...i] = target
• s[j...i] = s[i] - s[j-1] == target->s[j-1] = s[i] - target
• 再分析因为我们要求的是最大数目所以，我们对于每个i都应该找尽量“后面”的j来进行匹配

• 让[j,i]越小那么我们可能产生的子数组数量就会越多

• 通过一个HashMap<Integer,Integer>,{key}->前缀和,{val}->该前缀和"最后一次"出现的位置来记录前缀和消息和位置消息

时间复杂度(状态个数:N,状态转移:O(1)->O(N))

代码:

/**
* dp[i]:表示以i结尾的和为目标值的最大数目不重叠非空子数组数目
* 状态计算:由是否选择第i个字符来划分
*   1.不选:dp[i] = dp[i-1]
*   2.选 : dp[i] = dp[p-1] + 1; p表示离i最近的满足条件的位置
* 关键点:如何快速确定S[l...r]==target->前缀和
*   
*/
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n+1];
        //{key}->前缀和,{val}->"最后一次出现该前缀和"的位置
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,0);
        int sum = 0;
        for(int i = 1 ; i <= n ; i++){
            sum += nums[i-1];
            int need = sum - target;
            if(hash.containsKey(need)){
                dp[i] = Math.max(dp[i-1],dp[hash.get(need)]+1);
            }else{
                dp[i] = dp[i-1];
            }
            hash.put(sum,i);
        }
        return dp[n];
    }
}