当前位置:网站首页>LeetCode 1477. Find two subarrays with sum as the target value and no overlap
LeetCode 1477. Find two subarrays with sum as the target value and no overlap
2022-07-07 16:59:00 【@Little safflower】
Problem description
Give you an array of integers arr And an integer value target .
Please come in arr In looking for Two non overlapping subarrays And their sum is equal to target . There may be many options , Please return the sum of the length of the two sub arrays that meet the requirements minimum value .
Please return the minimum length and , If you can't find such two sub arrays , Please return -1 .
Example 1:
Input :arr = [3,2,2,4,3], target = 3
Output :2
explain : There are only two subarrays and 3 ([3] and [3]). Their length and are 2 .
Example 2:Input :arr = [7,3,4,7], target = 7
Output :2
explain : Even though we have 3 The sum of two non overlapping subarrays is 7 ([7], [3,4] and [7]), But we will choose the first and third sub arrays , Because of their length and 2 Is the minimum .
Example 3:Input :arr = [4,3,2,6,2,3,4], target = 6
Output :-1
explain : We have only one sum for 6 Subarray .
Example 4:Input :arr = [5,5,4,4,5], target = 3
Output :-1
explain : We can't find and for 3 Subarray .
Example 5:Input :arr = [3,1,1,1,5,1,2,1], target = 3
Output :3
explain : Notice the subarray [1,2] and [2,1] Can't be a solution because they overlap .
Tips :
1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8source : Power button (LeetCode)
link :https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Java
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int[] dp = new int[n];
// Minimum requirements , Fill with a larger number
Arrays.fill(dp,Integer.MAX_VALUE / 2);
int ans = Integer.MAX_VALUE;
// Double pointer
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;
}
}
边栏推荐
- 【DesignMode】享元模式(Flyweight Pattern)
- LeetCode 1986. 完成任务的最少工作时间段 每日一题
- skimage学习(3)——Gamma 和 log对比度调整、直方图均衡、为灰度图像着色
- SqlServer2014+: 创建表的同时创建索引
- [medical segmentation] attention Unet
- Lie cow count (spring daily question 53)
- LeetCode-SQL第一天
- 最新高频Android面试题目分享,带你一起探究Android事件分发机制
- LeetCode 1043. 分隔数组以得到最大和 每日一题
- node:504报错
猜你喜欢
随机推荐
Binary search tree (features)
[vulnhub range] thales:1
运算符
Opencv personal notes
DAPP defi NFT LP single and dual currency liquidity mining system development details and source code
typescript ts 基础知识之类型声明
Interface oriented programming
Pycharm IDE下载
QT视频传输
作为Android开发程序员,android高级面试
Three. JS series (2): API structure diagram-2
水平垂直居中 方法 和兼容
LeetCode 120. 三角形最小路径和 每日一题
Seaborn数据可视化
Opencv configuration 2019vs
LeetCode-SQL第一天
掌握这套精编Android高级面试题解析,oppoAndroid面试题
QT 图片背景色像素处理法
LeetCode 1626. 无矛盾的最佳球队 每日一题
网关Gateway的介绍与使用