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。

数据范围

• 序列长度：
• 序列中的每个数字和 的范围：

题解

前缀和+哈希表

1. 计算前缀和：遍历一次数组，计算到每个位置的累积和。
2. 使用哈希表记录前缀和：键是前缀和，值是该和第一次出现的索引。
3. 在计算前缀和的同时，检查是否存在 当前前缀和 - 目标和 的差值在哈希表中。

细节：

• 只需要遍历一次数组，时间复杂度为 O(N)。
• 使用哈希表可以在 O(1) 时间内查找之前的前缀和。

具体步骤：

1. 初始化前缀和为 0，最长子序列长度为 0。
2. 遍历数组，累加前缀和。
3. 如果 当前前缀和 - 目标和 存在于哈希表中，更新最长子序列长度。
4. 如果当前前缀和不在哈希表中，将其加入哈希表。

时间复杂度：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

functi