题目描述

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

样例

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]）。
但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

输入：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

算法分析

• 1、通过双指针算法找到符合条件的所有子数组，双指针i，j维护的是[i,j]区间的总值cur <= target，若cur > target,j向右移动，直到cur <= target
• 2、由于选两个符合条件且不重叠的子数组使得长度最小，f[i]表示的是右端点 <= i的最短长度，g[i]表示的是左端点 >= i的最短长度，枚举中间分界点i，ans = min(ans,f[i] + g[i + 1])
• 3、如何计算出f[i]，g[i]的值？
  • 对符合条件的所有区间按照右端点进行排序，枚举排序后每个区间，计算出以f[右端点]的最小值，由于是间隔计算，因此最后需要对f[i]进行补齐操作
  • g[i]则按照左端点进行排序，和上面同理

注意：3操作没想到什么好方法hh，应该还有更灵性的方法，仅供参考

时间复杂度 $O(n + klogk)$

n表示arr数组的长度，k表示找到符合条件的子数组个数

Java 代码

class Solution {
    static int INF = 0x3f3f3f3f;
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int cur = 0;
        Pair[] pair = new Pair[n];
        int k = 0;
        for(int i = 0,j = 0;i < n;i ++)
        {
            cur += arr[i];
            while(j < i && cur > target)
            {
                cur -= arr[j];
                j ++;
            } 
            if(cur == target)
            {
                pair[k ++] = new Pair(j,i,i - j + 1);
            }
        }

        Arrays.sort(pair,0,k,(x,y) -> (x.r - y.r));//按右端点排序
        int[] f = new int[n];// 从前i个中选，右端点 <= i的最短长度
        Arrays.fill(f, INF);
        int minv = INF;
        for(int i = 0;i < k;i ++)
        {
            if(pair[i].len < minv)
            {
                minv = pair[i].len;
            }
            f[pair[i].r] = minv;
        }
        //补齐操作
        for(int i = 1;i < n;i ++)
        {
            if(f[i] == INF) f[i] = f[i - 1];
        }

        Arrays.sort(pair,0,k,(x,y) -> (x.l - y.l));//按左端点排序
        int[] g = new int[n];// 从前i个中选，左端点 >= i的最短长度
        Arrays.fill(g, INF);
        minv = INF;
        for(int i = k - 1;i >= 0;i --)
        {
            if(pair[i].len < minv)
            {
                minv = pair[i].len;
            }
            g[pair[i].l] = minv;
        }
        //补齐操作
        for(int i = n - 2;i >= 0;i --)
        {
            if(g[i] == INF) g[i] = g[i + 1];
        }

        int ans = INF;
        for(int i = 0;i < n - 1;i ++)
        {
            ans = Math.min(ans, f[i] + g[i + 1]);
        }
        if(ans == INF) return -1;
        return ans;
    }
}
class Pair 
{
    int l,r,len;
    Pair(int l,int r,int len)
    {
        this.l = l;
        this.r = r;
        this.len = len;
    }
}