最长连续子序列 - 华为OD统一考试

OD统一考试(B卷)

分值: 100分

题解: Java / Python / C++

alt

题目描述

有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。

题解

数据量不大,简单的两层循环暴力即可。

Java

import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取整数数组
        int[] arr = Arrays.stream(scanner.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();

        int sum = scanner.nextInt(), result = -1;
        for (int i = 0; i < arr.length; i++) {
            int tot = 0;
            for (int j = i; j < arr.length; j++) {
                tot += arr[j];
                if (tot == sum) {
                    result = Math.max(result, j - i + 1);
                } else if (tot > sum) {
                    break;
                }
            }
        }

        System.out.println(result);
    }
}

Python

arr = list(map(int, input().split(',')))
sum, result = int(input()), -1

for i in range(len(arr)):
    tot = 0
    for j in range(i, len(arr)):
        tot += arr[j]
        if tot == sum:
            result = max(result, j - i + 1)
        elif tot > sum:
            break

print(result)

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> arr;
    int t, sum;
    while(cin >> t) {
        arr.push_back(t);
        if(cin.peek() == ',') {
            cin.ignore();
        } else {
            cin >> sum;
            break;
        }
    }

    int result = -1;
    for(int i = 0; i < arr.size(); i++) {
        for(int j = i, tot = 0; j < arr.size() && tot <= sum; j++) {
            tot += arr[j];
            if(tot == sum) {
                result = max(result, j - i + 1);
            }
        }
    }

    cout << result << endl;

    return 0;
}

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

#面经##华为##校招##秋招##春招#
全部评论
双指针
1 回复 分享
发布于 2024-03-01 11:29 广东
class Solution { public: int huawei(vector<int>& nums,int sum) { int prefix = 0; int ans = -1; unordered_map<int>mp; mp[0] = -1; // 特判 for(int i = 0; i</int></int>
1 回复 分享
发布于 2024-02-28 19:49 湖北
可以使用 前缀和与哈希表来实现. 哈希表记录值为prefix的前缀和的第一次出现的下标. 每遍历一个新的下标,在哈希表中查找current_prefix - num 对应的下标, 当前下标减去该下标即为所求值,最后取最大值即可.
1 回复 分享
发布于 2024-02-28 19:34 湖北
都是正整数可以用前缀和+双指针,时间复杂度O(n)
点赞 回复 分享
发布于 2024-03-14 10:58 江西
如遇到真题请勿直接抄袭代码,此代码仅供学习参考,有更好的解法,欢迎评论区留下
点赞 回复 分享
发布于 2024-02-28 18:07 湖北

相关推荐

05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
8
16
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务