E卷-最长连续子序列(100分)

最长连续子序列

问题描述

给定一个由 $N$ 个正整数组成的序列和一个目标和 $sum$ 。任务是找出最长的连续子序列，使得该子序列的元素和等于 $sum$ 。如果存在这样的子序列，返回其长度；如果不存在，则返回 $-1$ 。

输入格式

输入包含两行：

第一行是由英文逗号分隔的 $N$ 个正整数，表示输入序列。
第二行是一个正整数 $sum$ ，表示目标和。

输出格式

输出一个整数，表示满足条件的最长连续子序列的长度。如果不存在满足条件的子序列，输出 $-1$ 。

样例输入

1,2,3,4,2
6

样例输出

样例解释

序列 1,2,3 和 4,2 都满足和为 6 的条件，但 1,2,3 的长度为 3，是最长的，因此输出 3。

样例输入

1,2,3,4,2
20

样例输出

-1

样例解释

没有任何连续子序列的和等于 20，因此输出 -1。

数据范围

序列长度： $1 \leq N \leq 200$
序列中的每个数字和 $sum$ 的范围： $1 \leq num, sum \leq 10^9$

题解

前缀和+哈希表

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

细节：

只需要遍历一次数组，时间复杂度为 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语言哈希表实现起来比较困难，可以直接使用双指针的做法来替代
#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();
    }
}

#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刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记