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

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

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

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

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

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

动态规划

数组含义：

• d[i]表示到编号i（不包含i）的情况下满足target目标的最短子数组的长度

初始化

• 较大值表示无效

计算

• 因为是连续子数组，使用前缀和来解决，并且基于双指针很去计算范围即可
• d[i] 取决于两种情况
• 1.能构成target，则min(d[i-1],r-l+1) ，取更短的子数组
• 2.不能，则等于d[i-1], 即没找到直接取上一个情况的值 结果

计算d过程中不断计算满足条件的两个长度之和
优化： 一次遍历就可以解决，具体参见代码
通俗解释一下：
比如两个数组范围是i~j （3个数）另一组是i* ~ j*（2个数）
我们把i那一组连续子数组认为是长度最小的，当我们找到i所在的最短的子数组时，可以确定，i对应的子数组肯定之前已经出现过了。
之前我们用d数组来记录了满足target目标的最短子数组的长度。
对于每次更新时，我们用res来记录当前两个子数组的长度和，一直记录最小值，当找到最小的子数组长度时，长度和也就得到了。

class Solution {
public:
    int minSumOfLengths(vector& arr, int target) {
        int n = arr.size();
        // 预留一个0来避免边缘情况
        int d[n+1];
        memset(d, 0, sizeof(d));
        // 一个较大值
        d[0] = 0x1f1f1f1f;
        // 返回值，表示是否存在最小长度和（两个长度和，初始是个大值，一旦出现过一次满足条件，则变小，然后一直取最小）
        int res = INT_MAX;
        int l = 0;
        int r = 0;
        // 当前累加和
        int sum = 0;
        // 一次遍历就可以解决
        for (r = 0; r < n; ++r)
        {
            sum += arr[r];
            while (sum > target)
            {
                sum -= arr[l];
                ++l; //移动左指针
            }
            if (sum == target)
            {
                int curr = r - l + 1;
                // 之前的最大和d[i]和当前和之和
                res = min(res, d[l] + curr); 
                // 取更小的值
                d[r+1] = min(d[r], curr);
            }
            else
            {
                d[r+1] = d[r];
            }
        }
        return res > n  ? -1 : res;
    }
};