class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
}
};
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^51 <= arr[i] <= 10001 <= target <= 10^8原站题解
golang 解法, 执行用时: 100 ms, 内存消耗: 8.2 MB, 提交时间: 2023-09-23 10:52:30
/**
* 使用滑动窗口分别计算leftMin, rightMin的值
* leftMin[i]表示以i为结尾的数组的子数组和为target的最小长度
* rightMin[i]表示以i开始的数组的子数组和为target的最小长度
* 然后再得到leftMin[i] + rightMin[i+1] 的最小值，即为该题答案
*/
func minSumOfLengths(arr []int, target int) int {
var leftMin, rightMin = make([]int, len(arr)), make([]int, len(arr))
var i, j, sum, ans int
for j = 0; j < len(arr); j++ {
sum += arr[j]
for sum > target {
sum -= arr[i]
i++
}
if j == 0 {
leftMin[j] = math.MaxInt32
} else {
leftMin[j] = leftMin[j-1]
}
if sum == target {
diff := j - i + 1
if leftMin[j] > diff {
leftMin[j] = diff
}
}
}
j = len(arr) - 1
sum = 0
for i = len(arr) - 1; i >= 0; i-- {
sum += arr[i]
for sum > target {
sum -= arr[j]
j--
}
if i == len(arr)-1 {
rightMin[i] = math.MaxInt32
} else {
rightMin[i] = rightMin[i+1]
}
if sum == target {
diff := j - i + 1
if rightMin[i] > diff {
rightMin[i] = diff
}
}
}
ans = math.MaxInt32
for i = 0; i < len(arr)-1; i++ {
if leftMin[i] == math.MaxInt32 || rightMin[i+1] == math.MaxInt32 {
continue
}
if leftMin[i]+rightMin[i+1] < ans {
ans = leftMin[i] + rightMin[i+1]
}
}
if ans == math.MaxInt32 {
return -1
} else {
return ans
}
}
python3 解法, 执行用时: 476 ms, 内存消耗: 40.2 MB, 提交时间: 2023-09-23 10:51:31
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
n = len(arr)
res = n + 1
pre = {}
pre[0] = -1
dp = [float('inf')] * n
p = 0
for i, a in enumerate(arr):
p += a
dp[i] = dp[i - 1]
if (p - target) in pre:
cur = i - pre[p - target]
if pre[p - target] >= 0 and dp[pre[p - target]] != float('inf'):
res = min(res, cur + dp[pre[p - target]])
dp[i] = min(i - pre[p - target], dp[i - 1])
pre[p] = i
print(pre)
return -1 if res == n + 1 else res
java 解法, 执行用时: 7 ms, 内存消耗: 57.9 MB, 提交时间: 2023-09-23 10:50:55
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
// dp[j] 表示当前j以及j之前的满足条件的最小区间长度
int[] dp = new int[n];
// 注意不能设置为最大值，因为相加会溢出
Arrays.fill(dp, Integer.MAX_VALUE / 2);
int ans = Integer.MAX_VALUE;
for(int i = 0, j = 0, sum = 0; j < n; j++){
sum += arr[j];
while(i <= j && sum > target){
sum -= arr[i++];
}
// 找到满足条件的一个区间
if(sum == target){
dp[j] = j - i + 1;
if(i != 0){
ans = Math.min(ans, dp[i-1] + j - i + 1);
}
}
if(j != 0)
dp[j] = Math.min(dp[j], dp[j-1]);
}
return ans > arr.length ? -1 : ans;
}
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 83 MB, 提交时间: 2023-09-23 10:49:41
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int size = arr.size(), left = 0, right, sum = 0, minSumOfLens = INT_MAX;
vector<int> dp(size + 1, 0);
dp[0] = size + 1; // dp[i]表示区间[0,i)之间最短的和为target的子数组，先初始化为一个较大的数表示不存在。因为会做加法运算，不能初始化为INT_MAX
for (right = 0; right < size; ++right) {
sum += arr[right];
while (sum > target) {
sum -= arr[left++];
}
if (sum == target) {
int len = right - left + 1; // 区间[left,right]是一个和为target的子数组，该子数组长度为len
minSumOfLens = min(minSumOfLens, len + dp[left]); // 如果有解，我们遍历了所有的第二个子数组，同时加上它前面长度最短的第一个子数组就是答案
dp[right + 1] = min(dp[right], len); // 更新dp，取长度更小的一个
}
else {
dp[right + 1] = dp[right]; // 不是一个和为target的子数组，dp[i]保持不变
}
}
return minSumOfLens > size ? -1 : minSumOfLens; // 大于size说明没有找到两个不重叠的子数组
}
};
cpp 解法, 执行用时: 88 ms, 内存消耗: 79.9 MB, 提交时间: 2023-09-23 10:37:59
/**
* 定义 d[i]表示到编号i（不包含i）的情况下满足target目标的最短子数组的长度
* 初始化 较大值表示无效
*/
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);
// cout << l << "~" << r << " " << curr << " " << d[l] << " " << res << endl;
// 取更小的值
d[r+1] = min(d[r], curr);
}
else
{
d[r+1] = d[r];
}
}
return res > n ? -1 : res;
}
};