1477. 找两个和为目标值且不重叠的子数组【滑动窗口 + dp】

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 的子数组。

C代码：滑动窗口 + dp

/*
* 核心思路：
* 	1、滑动窗口；
* 	2、dp[]末尾始终保存 "满足条件（和为target）的滑动窗口的最短长度"
* 	3、有重叠部分：dp[l-1] + len > arrSize
*/int minSumOfLengths(int* arr, int arrSize, int target){int dp[arrSize];// 注意不能设置为最大值，因为相加会溢出;// memset函数是以字节为单位来赋值的，即每个字节（注意是字节）的赋值是相同的。// 如果赋值的数值的二进制超过了一个字节，那么函数取的是该数值的最后一个字节的值。// memset(dp, 0x3f, sizeof(dp)); memset(dp, 0x3f, sizeof(dp)); int minLen = INT_MAX;int l = 0, sum = 0;for(int i = 0; i < arrSize; i++){sum += arr[i];while(sum > target) {sum -= arr[l];++l;            // ☆ l始终指向："当前"滑动窗口的第一个值}                   // ☆ dp[l-1]：到数组下标l-1处，存在滑动窗口的最短值（满足和为target）if(sum == target){int len = i - l + 1;dp[i] = len;   // 每次相等、记录长度if (l != 0) {minLen = fmin(minLen, dp[l - 1] + len);}                 // 当前值len + dp[l-1]所需要的数组的最短长度 与 arrSize 对比; }                     // 第一次len + dp[0], minLen取最小值，初值自然要设为INT_MAX;if (i != 0) { dp[i] = fmin(dp[i], dp[i - 1]);  // 更新数组dp[]末尾为"最小值"}                     }                            // dp[i] = len 未赋值，则dp[i] = fmin(INT_MAX, dp[i - 1]);return minLen > arrSize ? -1 : minLen;
}