题目大意：
找两个和为目标值且不重叠的子数组
给你一个整数数组 arr 和一个整数值 target 。
请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。
请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。
示例 1：
输入：arr = [3,2,2,4,3], target = 3 输出：2 解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
示例 2：
输入：arr = [7,3,4,7], target = 7 输出：2 解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。
示例 3：
输入：arr = [4,3,2,6,2,3,4], target = 6 输出：-1 解释：我们只有一个和为 6 的子数组。
示例 4：
输入：arr = [5,5,4,4,5], target = 3 输出：-1 解释：我们无法找到和为 3 的子数组。
示例 5：
输入：arr = [3,1,1,1,5,1,2,1], target = 3 输出：3 解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。
提示：
1 <= arr.length <= 10^51 <= arr[i] <= 10001 <= target <= 10^8
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1477
解题思路分析：
- 使用滑动窗口找到所有和为target的区间，并将区间信息保存至list
- 将list内区间按照长度排序
- 使用2层循环，两两比较每个区间，如果他们不重合，则使用他们的区间长度和更新全局最小值。（注意剪枝）
实现代码：
public int minSumOfLengths(int[] arr, int target) {
int sum=0; // 区间和
int left=0,right=0; // 区间左右指针
List<int[]> list=new ArrayList<>(); // 记录所有和为target的区间
while(right<arr.length){ // 滑动窗口来找到所有符合条件的区间
sum+=arr[right]; // 累加区间和
if(sum==target){ // 区间和等于target
list.add(new int[]{left,right}); // 将当前区间存入list
}else if(sum>target){ // 如果区间和大于target
while(sum>target&&left<=right){ // 减少左区间以减少区间和
sum-=arr[left];
left++;
}
if(sum==target){ // 移动完左区间后，当前区间和等于target
list.add(new int[]{left,right}); // 将当前区间存入list
}
}
right++; // 移动右区间
}
if(list.size()<2) return -1; // 如果合理区间不足2个，返回-1。
// 将所有区间按照区间长度排序
Collections.sort(list,(int[] a,int[] b)->(a[1]-a[0])-(b[1]-b[0]));
// 返回结果（最小区间和）
int min=Integer.MAX_VALUE;
// 循环每一个区间
for(int i=0;i<list.size();i++){
int[] arr1=list.get(i); // 当前区间
int length1=arr1[1]-arr1[0]+1; // 当前区间长度
// 当前区间长度大于返回结果，退出
// 因为数组已排序，若当前区间长度大于等于min的话，后面的也一定大于
if(length1>=min) break;
for(int j=i+1;j<list.size();j++){ // 循环第二个区间
int[] arr2=list.get(j); // 第二个区间
int length2=arr2[1]-arr2[0]+1; // 第二个区间长度
if(length1+length2>=min) break; // 2个区间长度和大于返回结果，退出当前循环
if(!isOverlap(arr1,arr2)){ // 如果两个区间不重合，用区间长度和去更新min
min=Math.min(min,length1+length2);
}
}
}
return min==Integer.MAX_VALUE?-1:min;
}
boolean isOverlap(int[] a,int[] b){
return a[1]>=b[0]&&a[1]<=b[1] || a[0]>=b[0]&&a[0]<=b[1];
}本题解法执行时间为31ms。
Runtime: 31 ms, faster than 66.57% of Java online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.
Memory Usage: 95.6 MB, less than 100.00% of Java online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1477-find-two-non-overlapping-sub-arrays-each-with-target-sum-解题思路分析/