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 的最短的数组len
    vector<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 的最短的数组len
    vector<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-/