给你一个整数数组 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<int>& 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; } };
