当前位置:网站首页>LeetCode 1477. 找两个和为目标值且不重叠的子数组 每日一题
LeetCode 1477. 找两个和为目标值且不重叠的子数组 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给你一个整数数组 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^5
1 <= arr[i] <= 1000
1 <= target <= 10^8来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int[] dp = new int[n];
//要求最小,填充为较大的数
Arrays.fill(dp,Integer.MAX_VALUE / 2);
int ans = Integer.MAX_VALUE;
//双指针
int left = 0;
int sum = 0;
for(int right = 0;right < n;right++){
sum += arr[right];
while(left <= right && sum > target){
sum -= arr[left++];
}
if(sum == target){
dp[right] = right - left + 1;
if(left != 0){
ans = Math.min(ans,dp[left - 1] + dp[right]);
}
}
if(right != 0){
dp[right] = Math.min(dp[right - 1],dp[right]);
}
}
return ans > n ? -1 : ans;
}
}
边栏推荐
猜你喜欢
Personal notes of graphics (1)
ByteDance Android gold, silver and four analysis, Android interview question app
Spark Tuning (III): persistence reduces secondary queries
低代码(lowcode)帮助运输公司增强供应链管理的4种方式
《产品经理必读:五种经典的创新思维模型》的读后感
【DesignMode】代理模式(proxy pattern)
[medical segmentation] attention Unet
[designmode] proxy pattern
最新2022年Android大厂面试经验,安卓View+Handler+Binder
字节跳动Android金三银四解析,android面试题app
随机推荐
[medical segmentation] attention Unet
[vulnhub range] thales:1
OpenGL personal notes
JS中null NaN undefined这三个值有什么区别
Ray and OBB intersection detection
Tragedy caused by deleting the console statement
LeetCode 1031. 两个非重叠子数组的最大和 每日一题
Personal notes of graphics (4)
time标准库
水平垂直居中 方法 和兼容
作为Android开发程序员,android高级面试
记一次项目的迁移过程
Lie cow count (spring daily question 53)
ATM系统
掌握这个提升路径,面试资料分享
编程模式-表驱动编程
字节跳动高工面试,轻松入门flutter
LeetCode 1186. 删除一次得到子数组最大和 每日一题
最新Android面试合集,android视频提取音频
Prometheus API deletes all data of a specified job