文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：和为目标值且不重叠的非空子数组的最大数目
出处：1546. 和为目标值且不重叠的非空子数组的最大数目
难度
6 级
题目描述
要求
给定一个数组nums \texttt{nums}nums和一个整数target \texttt{target}target，返回子数组元素和为target \texttt{target}target的非空不重叠子数组的最大数目。
示例
示例 1：
输入：nums = [1,1,1,1,1], target = 2 \texttt{nums = [1,1,1,1,1], target = 2}nums = [1,1,1,1,1], target = 2
输出：2 \texttt{2}2
解释：总共有2 \texttt{2}2个不重叠子数组（下划线表示）[ 1,1 ‾ ,1, 1,1 ‾ ] \texttt{[\underline{1,1},1,\underline{1,1}]}[1,1,1,1,1]满足和为目标值2 \texttt{2}2。
示例 2：
输入：nums = [-1,3,5,1,4,2,-9], target = 6 \texttt{nums = [-1,3,5,1,4,2,-9], target = 6}nums = [-1,3,5,1,4,2,-9], target = 6
输出：2 \texttt{2}2
解释：总共有3 \texttt{3}3个子数组和为6 \texttt{6}6：[5,1] \texttt{[5,1]}[5,1]、[4,2] \texttt{[4,2]}[4,2]、[3,5,1,4,2,-9] \texttt{[3,5,1,4,2,-9]}[3,5,1,4,2,-9]，但只有前2 \texttt{2}2个是不重叠的。
数据范围
- 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5}1≤nums.length≤105
- -10 4 ≤ nums[i] ≤ 10 4 \texttt{-10}^\texttt{4} \le \texttt{nums[i]} \le \texttt{10}^\texttt{4}-104≤nums[i]≤104
- 0 ≤ target ≤ 10 6 \texttt{0} \le \texttt{target} \le \texttt{10}^\texttt{6}0≤target≤106
解法
思路和算法
为了计算元素和为target \textit{target}target的非空不重叠子数组的最大数目，需要计算数组nums \textit{nums}nums的前缀和并使用哈希表存储每个前缀和对应的下标。如果数组nums \textit{nums}nums的下标i ii处的前缀和是sum \textit{sum}sum，下标prev \textit{prev}prev处的前缀和是sum − target \textit{sum} - \textit{target}sum−target，其中prev < i \textit{prev} < iprev<i，则数组nums \textit{nums}nums的下标范围[ prev + 1 , i ] [\textit{prev} + 1, i][prev+1,i]的子数组的元素和是target \textit{target}target。
根据贪心策略，为了使元素和为target \textit{target}target的非空不重叠子数组的数目最大化，在选取元素和为target \textit{target}target的子数组时应将每个子数组的长度最小化。为了使每个元素和为target \textit{target}target的子数组长度最小化，哈希表中应存储每个前缀和最后一次出现的下标。
由于空前缀不包含任何元素，即空前缀的元素和是0 00，因此首先将前缀和0 00与下标− 1 -1−1存入哈希表。将上一个子数组的结束下标记为prev \textit{prev}prev，将前缀和记为sum \textit{sum}sum，初始时prev = − 1 \textit{prev} = -1prev=−1，sum = 0 \textit{sum} = 0sum=0。遍历数组nums \textit{nums}nums，当遍历到下标i ii时，执行如下操作。
将sum \textit{sum}sum增加nums [ i ] \textit{nums}[i]nums[i]，此时sum \textit{sum}sum为下标i ii处的前缀和。
如果哈希表中存在前缀和sum − target \textit{sum} - \textit{target}sum−target且前缀和sum − target \textit{sum} - \textit{target}sum−target最后一次出现的下标大于等于prev \textit{prev}prev，则得到一个元素和为target \textit{target}target且与上一个子数组不重叠的子数组，将子数组数目加1 11，将prev \textit{prev}prev更新为i ii，表示遍历当前子数组之后，上一个子数组的结束下标变成i ii。
前缀和sum \textit{sum}sum的最后一次出现的下标是i ii，将前缀和sum \textit{sum}sum与下标i ii存入哈希表。
遍历结束之后，即可得到元素和为target \textit{target}target的非空不重叠子数组的最大数目。
上述贪心策略的正确性说明如下。
如果有多个以同一个下标结尾的子数组的元素和都是target \textit{target}target，则选取其中的长度最小的子数组。理由如下：如果数组nums \textit{nums}nums的下标i ii处的前缀和是sum \textit{sum}sum，下标prev 1 \textit{prev}_1prev1和prev 2 \textit{prev}_2prev2处的前缀和都是sum − target \textit{sum} - \textit{target}sum−target，其中prev 1 < prev 2 < i \textit{prev}_1 < \textit{prev}_2 < iprev1<prev2<i，则数组nums \textit{nums}nums的下标范围[ prev 1 + 1 , i ] [\textit{prev}_1 + 1, i][prev1+1,i]和[ prev 2 + 1 , i ] [\textit{prev}_2 + 1, i][prev2+1,i]的两个子数组都满足元素和是target \textit{target}target，下标范围[ 0 , prev 1 ] [0, \textit{prev}_1][0,prev1]的前缀长度小于下标范围[ 0 , prev 2 ] [0, \textit{prev}_2][0,prev2]的前缀长度，在下标范围[ 0 , prev 1 ] [0, \textit{prev}_1][0,prev1]中的子数组一定在下标范围[ 0 , prev 2 ] [0, \textit{prev}_2][0,prev2]中，但是在下标范围[ 0 , prev 2 ] [0, \textit{prev}_2][0,prev2]中的子数组不一定在下标范围[ 0 , prev 1 ] [0, \textit{prev}_1][0,prev1]中，因此下标范围[ 0 , prev 2 ] [0, \textit{prev}_2][0,prev2]中的元素和为target \textit{target}target的子数组数目一定大于等于下标范围[ 0 , prev 1 ] [0, \textit{prev}_1][0,prev1]中的元素和为target \textit{target}target的子数组数目，选取下标范围[ prev 2 + 1 , i ] [\textit{prev}_2 + 1, i][prev2+1,i]的子数组可以得到的元素和为target \textit{target}target的子数组数目一定大于等于选取下标范围[ prev 1 + 1 , i ] [\textit{prev}_1 + 1, i][prev1+1,i]的子数组可以得到的元素和为target \textit{target}target的子数组数目。
如果存在以下标i ii结尾的元素和为target \textit{target}target的子数组，且该子数组与之前的元素和为target \textit{target}target的子数组不重叠，则选取以下标i ii结尾的当前子数组。理由如下：如果不选取以下标i ii结尾的元素和为target \textit{target}target的子数组，而是选取以更大下标j jj结尾的元素和为target \textit{target}target的子数组，则以下标i + 1 i + 1i+1开始的后缀长度大于以下标j + 1 j + 1j+1开始的后缀长度，以下标j + 1 j + 1j+1开始的后缀中的子数组一定在以下标i + 1 i + 1i+1开始的后缀中，但是以下标i + 1 i + 1i+1开始的后缀中的子数组不一定在以下标j + 1 j + 1j+1开始的后缀中，因此以下标i + 1 i + 1i+1开始的后缀中的元素和为target \textit{target}target的子数组数目一定大于等于以下标j + 1 j + 1j+1开始的后缀中的元素和为target \textit{target}target的子数组数目，选取以下标i ii结尾的子数组可以得到的元素和为target \textit{target}target的子数组数目一定大于等于选取以下标j jj结尾的子数组可以得到的元素和为target \textit{target}target的子数组数目。
代码
classSolution{publicintmaxNonOverlapping(int[]nums,inttarget){intsubarrays=0;Map<Integer,Integer>indices=newHashMap<Integer,Integer>();indices.put(0,-1);intprev=-1;intsum=0;intlength=nums.length;for(inti=0;i<length;i++){sum+=nums[i];if(indices.containsKey(sum-target)){if(indices.get(sum-target)>=prev){subarrays++;prev=i;}}indices.put(sum,i);}returnsubarrays;}}复杂度分析
时间复杂度：O ( n ) O(n)O(n)，其中n nn是数组nums \textit{nums}nums的长度。遍历数组一次，对于数组中每个元素的操作时间都是O ( 1 ) O(1)O(1)。
空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组nums \textit{nums}nums的长度。哈希表需要O ( n ) O(n)O(n)的空间。
