最长连续子序列 - 华为OD统一考试
OD统一考试(B卷)
分值: 100分
题解: Java / Python / C++
题目描述
有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;
}
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
#面经##华为##校招##秋招##春招#