【华为OD题库-084】最长连续子序列-Java

这篇具有很好参考价值的文章主要介绍了【华为OD题库-084】最长连续子序列-Java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

有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://blog.csdn.net/qq_31076523/article/details/134176793。百度和各类采集站皆不可信,搜索请谨慎鉴别。技术类文章一般都有时效性,本人习惯不定期对自己的博文进行修正和更新,因此请访问出处以查看本文的最新版本。文章来源地址https://www.toymoban.com/news/detail-756469.html

到了这里,关于【华为OD题库-084】最长连续子序列-Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 799. 最长连续不重复子序列 java

    目录 算法描述 输入格式 输出格式 数据范围 输入样例: 输出样例: 代码 算法分析 给定一个长度为 n� 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。 输入格式 第一行包含整数 n�。 第二行包含 n� 个整数(均在 0∼1050∼105 范围内),表示整

    2024年02月06日
    浏览(31)
  • leetcode 516. 最长回文子序列(JAVA)题解

    题目链接 https://leetcode.cn/problems/longest-palindromic-subsequence/description/?utm_source=LCUSutm_medium=ip_redirectutm_campaign=transfer2china 目录 题目描述: 暴力递归: 动态规划: 给你一个字符串  s  ,找出其中最长的回文子序列,并返回该序列的长度。子序列定义为:不改变剩余字符顺序的情况

    2024年02月13日
    浏览(41)
  • 【华为OD题库-083】玩牌高手-Java

    给定一个长度为n的整型数组,表示一个选手在n轮内可选择的牌面分数。选手基于规则选牌,请计算所有轮结束后其可以获得的最高总分数。 选择规则如下: 1.在每轮里选手可以选择获取该轮牌面,则其总分数加上该轮牌面分数,为其新的总分数。 2.选手也可不选择本轮牌面直

    2024年02月04日
    浏览(45)
  • 华为OD机试 - 最长公共后缀(Java & JS & Python)

    题目描述 编写一个函数来查找字符串数组中的最长公共后缀; 如果不存在公共后缀,返回固定字符串: @Zero。 补充说明: 字符串长度范围:[2, 1000] 字符串中字符取值范围为[1, 126] 输入描述 无 输出描述 无 用例 输入 [\\\"abc\\\",\\\"bbc\\\",\\\"c\\\"] 输出 \\\"c\\\" 说明 返回公共后缀: c 输入 [\\\"aa\\\",\\\"b

    2024年02月13日
    浏览(52)
  • 华为OD-非严格递增连续数字序列

    输入一个字符串仅包含大小写字母和数字 求字符串中包含的最长的非严格递增连续数字序列长度 比如: 12234属于非严格递增数字序列 输入一个字符串仅包含大小写字母和数字 输出字符串中包含的最长的非严格递增连续数字序列长度 输入 输出 2234 为最长的非严格递增连续数

    2024年02月11日
    浏览(40)
  • 【免费题库】华为OD题库C卷 - API集群负载统计(Java 代码+解析)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 某个产品的RESTful API集合部署在服务器集群的多个节点上,近期对客户端访问日志进行了采集,需要统计各个API的访问频次,根据热点信息在服务器节点之间做负载均衡,现在需要实

    2024年04月13日
    浏览(46)
  • 华为OD机试 - 最长合法表达式(Java & JS & Python & C)

    题目描述 提取字符串中的最长合法简单数学表达式,字符串长度最长的,并计算表达式的值。如果没有,则返回 0 。 简单数学表达式只能包含以下内容: 0-9数字,符号+-* 说明: 所有数字,计算结果都不超过long 如果有多个长度一样的,请返回第一个表达式的结果 数学表达

    2024年02月04日
    浏览(42)
  • 华为OD机试 - 寻找符合要求的最长子串(Java & JS & Python)

    题目描述 给定一个字符串s,找出这样一个子串: 该子串中任意一个字符最多出现2次 该子串不包含指定某个字符 请你找出满足该条件的最长子串的长度 输入描述 第一行为:要求不包含的指定字符,为单个字符,取值范围[0-9a-zA-Z] 第二行为:字符串s,每个字符范围[0-9a-zA-

    2024年02月05日
    浏览(46)
  • 【免费题库】华为OD题库C卷 - We Are A Team(Java 代码+解析)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 总共有 n 个人在机房,每个人有一个标号(1=标号=n),他们分成了多个团队,需要你根据收到的 m 条消息判定指定的两个人是否在一个团队中,具体的: 消息构成为 a b c,整数 a、

    2024年04月12日
    浏览(45)
  • 矩阵匹配【华为OD机试JAVA&Python&C++&JS题解】

    从一个N M(N=M)的矩阵中选出N个数,任意两个数字不能在同一行或同一列,求选出来的N个数中第K大的数字的最小值是多少。 输入描述: 输入矩阵要求:1=K=N=M=150 输入格式:N M K N M矩阵 输出描述: N*M的矩阵中可以选出M!/N!种组合数组,每个组合数组中第K大的数中的最小值。

    2024年04月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包