E卷-最长连续子序列(100分)
最长连续子序列
问题描述
给定一个由 个正整数组成的序列和一个目标和 。任务是找出最长的连续子序列,使得该子序列的元素和等于 。如果存在这样的子序列,返回其长度;如果不存在,则返回 。
输入格式
输入包含两行:
- 第一行是由英文逗号分隔的 个正整数,表示输入序列。
- 第二行是一个正整数 ,表示目标和。
输出格式
输出一个整数,表示满足条件的最长连续子序列的长度。如果不存在满足条件的子序列,输出 。
样例输入
1,2,3,4,2
6
样例输出
3
样例解释
序列 1,2,3 和 4,2 都满足和为 6 的条件,但 1,2,3 的长度为 3,是最长的,因此输出 3。
样例输入
1,2,3,4,2
20
样例输出
-1
样例解释
没有任何连续子序列的和等于 20,因此输出 -1。
数据范围
- 序列长度:
- 序列中的每个数字和 的范围:
题解
前缀和+哈希表
- 计算前缀和:遍历一次数组,计算到每个位置的累积和。
- 使用哈希表记录前缀和:键是前缀和,值是该和第一次出现的索引。
- 在计算前缀和的同时,检查是否存在
当前前缀和 - 目标和
的差值在哈希表中。
细节:
- 只需要遍历一次数组,时间复杂度为 O(N)。
- 使用哈希表可以在 O(1) 时间内查找之前的前缀和。
具体步骤:
- 初始化前缀和为 0,最长子序列长度为 0。
- 遍历数组,累加前缀和。
- 如果
当前前缀和 - 目标和
存在于哈希表中,更新最长子序列长度。 - 如果当前前缀和不在哈希表中,将其加入哈希表。
时间复杂度:O(N),其中 N 是序列的长度。 空间复杂度:O(N),用于存储哈希表。
参考代码
- Python
def longest_subarray_sum(nums, target_sum):
# 初始化前缀和字典,键为前缀和,值为索引
prefix_sum = {0: -1}
current_sum = 0
max_length = -1
# 遍历数组
for i, num in enumerate(nums):
# 更新当前和
current_sum += num
# 检查是否存在一个之前的前缀和,使得当前和减去它等于目标和
if current_sum - target_sum in prefix_sum:
# 更新最大长度
max_length = max(max_length, i - prefix_sum[current_sum - target_sum])
# 如果当前和不在字典中,添加它
if current_sum not in prefix_sum:
prefix_sum[current_sum] = i
return max_length
# 读取输入
nums = list(map(int, input().split(',')))
target_sum = int(input())
# 计算并输出结果
result = longest_subarray_sum(nums, target_sum)
print(result)
- C
// C语言哈希表实现起来比较困难,可以直接使用双指针的做法来替代
#include <stdio.h>
// 定义最大值宏
#define MAX(a, b) ((a) > (b) ? (a) : (b))
// 定义数组最大大小
#define MAX_SIZE 200000
// 函数原型声明
int longestSubarraySum(int nums[], int nums_size, long long target_sum);
int main() {
int nums[MAX_SIZE];
int nums_size = 0;
char c;
// 读取输入数组
while (scanf("%d%c", &nums[nums_size], &c) == 2) {
nums_size++;
if (c != ',') break;
}
long long target_sum;
scanf("%lld", &target_sum);
// 计算并输出结果
printf("%d\n", longestSubarraySum(nums, nums_size, target_sum));
return 0;
}
int longestSubarraySum(int nums[], int nums_size, long long target_sum) {
int max_length = -1;
int left = 0, right = 0;
long long current_sum = 0;
// 使用双指针遍历数组
while (right < nums_size) {
// 扩展右指针,增加当前和
current_sum += nums[right];
// 如果当前和大于目标和,收缩左指针
while (current_sum > target_sum && left <= right) {
current_sum -= nums[left];
left++;
}
// 如果当前和等于目标和,更新最大长度
if (current_sum == target_sum) {
max_length = MAX(max_length, right - left + 1);
}
right++;
}
return max_length;
}
- Javascript
function longestSubarraySum(nums, targetSum) {
// 初始化前缀和Map,键为前缀和,值为索引
const prefixSum = new Map();
prefixSum.set(0, -1);
let currentSum = 0;
let maxLength = -1;
// 遍历数组
for (let i = 0; i < nums.length; i++) {
// 更新当前和
currentSum += nums[i];
// 检查是否存在一个之前的前缀和,使得当前和减去它等于目标和
if (prefixSum.has(currentSum - targetSum)) {
// 更新最大长度
maxLength = Math.max(maxLength, i - prefixSum.get(currentSum - targetSum));
}
// 如果当前和不在Map中,添加它
if (!prefixSum.has(currentSum)) {
prefixSum.set(currentSum, i);
}
}
return maxLength;
}
// 读取输入
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let nums, targetSum;
rl.question('', (input) => {
nums = input.split(',').map(Number);
rl.question('', (input) => {
targetSum = parseInt(input);
const result = longestSubarraySum(nums, targetSum);
console.log(result);
rl.close();
});
});
- Java
import java.util.*;
public class Main {
public static int longestSubarraySum(int[] nums, long targetSum) {
// 初始化前缀和Map,键为前缀和,值为索引
Map<Long, Integer> prefixSum = new HashMap<>();
prefixSum.put(0L, -1);
long currentSum = 0;
int maxLength = -1;
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 更新当前和
currentSum += nums[i];
// 检查是否存在一个之前的前缀和,使得当前和减去它等于目标和
if (prefixSum.containsKey(currentSum - targetSum)) {
// 更新最大长度
maxLength = Math.max(maxLength, i - prefixSum.get(currentSum - targetSum));
}
// 如果当前和不在Map中,添加它
if (!prefixSum.containsKey(currentSum)) {
prefixSum.put(currentSum, i);
}
}
return maxLength;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入序列
String[] input = scanner.nextLine().split(",");
int[] nums = new int[input.length];
for (int i = 0; i < input.length; i++) {
nums[i] = Integer.parseInt(input[i]);
}
// 读取目标和
long targetSum = scanner.nextLong();
// 计算并输出结果
int result = longestSubarraySum(nums, targetSum);
System.out.println(result);
scanner.close();
}
}
- Cpp
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <string>
using namespace std;
int longestSubarraySum(const vector<int>& nums, long long targetSum) {
// 初始化前缀和哈希表,键为前缀和,值为索引
unordered_map<long long, int> prefixSum;
prefixSum[0] = -1;
long long currentSum = 0;
int maxLength = -1;
// 遍历数组
for (int i = 0; i < nums.size(); ++i) {
// 更新当前和
currentSum += nums[i];
// 检查是否存在一个之前的前缀和,使得当前和减去它等于目标和
if (prefixSum.find(currentSum - targetSum) != prefixSum.end()) {
// 更新最大长度
maxLength = max(maxLength, i - prefixSum[currentSum - targetSum]);
}
// 如果当前和不在哈希表中,添加它
if (prefixSum.find(currentSum) == prefixSum.end()) {
prefixSum[currentSum] = i;
}
}
return maxLength;
}
int main() {
string input;
getline(cin, input);
// 解析输入序列
vector<int> nums;
stringstream ss(input);
string token;
while (getline(ss, token, ',')) {
nums.push_back(stoi(token));
}
// 读取目标和
long long targetSum;
cin >> targetSum;
// 计算并输出结果
int result = longestSubarraySum(nums, targetSum);
cout << result << endl;
return 0;
}
#OD#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记