题目
有N个正整数组成的一个序列。给定整数sum,求长度最长的连续子序列,使他们的和等于sum,返回此子序列的长度。如果没有满足要求的序列,返回-1。
输入描述
第一行输入是:N个正整数组成的一个序列
第二行输入是:给定整数sum
输出描述
最长的连续子序列的长度
备注
输入序列仅由数字和英文逗号构成,数字之间采用英文逗号分隔。序列长度:1<=N<= 200
输入序列不考虑异常情况
示例1:
输入
1,2,3,4,2
6
输出
3
说明
1,2,3和4,2两个序列均能满足要求,所以最长的连续序列为1,2,3,因此结果为3.
示例2:
输入
1,2,3,4,2
20
输出
-1
说明
没有满足要求的子序列,返回-1
思路
滑动窗口法,以示例数据为例:1 2 3 4 2,目标和targetSum为6
记i为窗口左边界,j为窗口右边界,输入的数组为nums,初始和为curSum=nums[0]
如果curSum<targetSum,那么将j右移动,并更新当前curSum+=nums[++j],先右移再更新,可能越界
如果curSum==targetSum,那么记录此时窗口的长度:j-i+1
如果curSum>targetSum,那么i右移,并更新当前curSum-=nums[i–],先更新再右移,不会越界
最后考虑窗口保证有效,i,j不得超过nums范围,循环条件注意加上:i<=j,否则:1 2 3 4 2,目标和为0,无法通过。
题解
package hwod;
import java.util.Arrays;
import java.util.Scanner;
public class TheLongestContinueSubStr {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
int sum = sc.nextInt();
System.out.println(theLongestContinueSubStr(nums, sum));
}
private static int theLongestContinueSubStr(int[] nums, int sum) {
int i = 0, j = 0, res = -1;
int curSum = nums[0];
while (i <= j && i < nums.length && j < nums.length) {
if (curSum < sum) {
j++;
if (j < nums.length) curSum += nums[j];
} else if (curSum >= sum) {
if (curSum == sum) res = Math.max(res, j - i + 1);
curSum -= nums[i];
i++;
}
}
return res;
}
}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。文章来源:https://www.toymoban.com/news/detail-756469.html
说明
本专栏所有文章均为原创,欢迎转载,请注明文章出处:https://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信,搜索请谨慎鉴别。技术类文章一般都有时效性,本人习惯不定期对自己的博文进行修正和更新,因此请访问出处以查看本文的最新版本。文章来源地址https://www.toymoban.com/news/detail-756469.html
到了这里,关于【华为OD题库-084】最长连续子序列-Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!