1477. 找两个和为目标值且不重叠的子数组

本文主要是介绍1477. 找两个和为目标值且不重叠的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述 ：

给你一个整数数组 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^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

解题思路：

首先是确定边界，相当于将字符串切割为两个部分，左边找到一组值为target ，右边找到一组值为target；len（左边） + len(右边) 最小的那一个就是所要的结果。

每一部分每个位置在找到最小的len值即可； 递归的思路
以i 为右边界 (左->右)： i in （0，arr.size() - 1 ） len(0 - i) = min （len（0 -> i - 1），len（0->i）） ;
同理 以 i 为左边界 (右->左) i in （0，arr.size() - 1） len(arr.size() - 1 -> i) = min （len（arr.size() - 1 -> i - 1），len（arr.size() - 1 -> i）） ;

代码实现：

class Solution {
public:int minSumOfLengths(vector<int>& arr, int target) {int i , j ;int ret = 200000 ;int leftI = 0 , rightE = arr.size() - 1;int sumR = 0 ;// 以 j当前值为左侧的端点，在 j - arr.size() - 1 之间 寻找 == target 的最短的数组lenvector<int> rightMin(arr.size() , 200000) ;for (j = rightE ; j > -1 ; j --){sumR += arr[j] ;while (sumR > target){sumR -= arr[rightE] ;rightE -- ;}if (sumR == target){if (j != arr.size() - 1)rightMin[j] = rightMin[j + 1] > (rightE - j + 1) ? (rightE - j + 1) : rightMin[j + 1] ;else {rightMin[j] = rightE - j + 1 ;}}if (j != arr.size() - 1)rightMin[j] = rightMin[j] > rightMin[j + 1] ? rightMin[j + 1] : rightMin[j] ;//}// 以 i当前值为右侧的端点，在 0 - i 之间 寻找 == target 的最短的数组lenvector<int> leftMin(arr.size(), 200000) ;sumR = 0 ;for (i = 0 ; i < arr.size() ; i ++){sumR += arr[i] ;while (sumR > target){sumR -= arr[leftI] ;leftI ++ ;}if (sumR == target){if (i != 0)leftMin[i] = leftMin[i - 1] > (i - leftI + 1) ? (i - leftI + 1) :leftMin[i - 1] ;else leftMin[i] = i - leftI + 1 ;}if (i != 0)leftMin[i] > leftMin[i - 1] ? leftMin[i - 1] : leftMin[i] ;}for (i = 0 ; i < arr.size() -  1 ; i ++)ret = ret > (leftMin[i] + rightMin[i + 1]) ? (leftMin[i] + rightMin[i + 1]) : ret ;if (ret >= 200000)return - 1 ;else return ret ;}
};

作者：tsmart
链接：https://leetcode-cn.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/solution/zhao-liang-ge-he-wei-mu-biao-zhi-qie-bu-zhong-die-/

这篇关于1477. 找两个和为目标值且不重叠的子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---