题面解释:

给定一个由正整数组成的序列（以英文逗号分隔），和一个目标整数 $sum$。要求找出序列中和等于 $sum$ 的最长连续子序列，并返回其长度。如果不存在满足要求的子序列，则返回 $-1$。例如，输入“1,2,3,4,2”和 $sum$ 为 $6$ 时，输出应为 $3$，因为子序列“1,2,3”的和等于 $6$，长度为 $3$。如果没有符合条件的子序列，返回 $-1$。

思路

1. 前缀和的定义：

   • 我们可以利用前缀和来计算区间的和。前缀和数组 pre[i] 表示从序列的起点到第 i 个元素的和，即 pre[i] = a[1] + a[2] + ... + a[i]。
   • 那么区间 [i, j] 的和可以表示为：pre[j] - pre[i-1]。这样可以通过常数时间计算任意区间的和。

2. 枚举区间：

   • 由于题目数据规模较小（$1 \leq N \leq 200$），我们可以通过两层循环枚举所有的区间。对于每个区间 [i, j]，计算它的和，并判断是否等于目标和 sum。
   • 如果满足条件，记录当前区间的长度，并更新最长的长度结果。

3. 边界情况：

   • 如果没有任何区间的和等于目标值 sum，返回 -1。

复杂度分析

• 时间复杂度：两层循环枚举区间，因此时间复杂度为 $O(N^2)$，其中 $N$ 是输入序列的长度。由于 $N \leq 200$，该复杂度可以在题目约束下接受。
• 空间复杂度：我们使用了一个前缀和数组，空间复杂度为 $O(N)$。

c++

#include <bits/stdc++.h>
using namespace std;

const int N = 210;  // 定义数组最大长度为210，包含1到200个元素的输入序列
int pre[N], sum;    // pre数组用于存储前缀和，sum存储目标和

int main()
{
    int x;          // 用于存储输入的数字
    int n = 0;      // 计数输入序列的长度

    // 读取输入序列，支持用逗号分隔
    while(cin >> x)  // 从标准输入读取数字
    {
        ++n;  // 序列长度+1
        pre[n] = pre[n-1] + x;  // 更新前缀和，pre[n]存储从序列开头到第n个元素的和
        if(getchar() != ',') break;  // 检查下一个字符是否是逗号，不是则停止输入
    }

    // 读取目标和
    cin >> sum;

    int res = -1;  // 初始化结果为-1，表示如果没有符合条件的子序列，返回-1

    // 枚举所有区间[i, j]
    for(int i = 1; i <= n; i++)  // 枚举区间起点i
    {
        for(int j = i; j <= n; j++)  // 枚举区间终点j
        {
            // 计算区间[i, j]的和，并检查是否等于sum
            if(pre[j] - pre[i-1] == sum)
            {
                // 更新结果为当前区间的长度
                res = max(res, j - i + 1);
            }
        }
    }

    // 输出最终结果，如果找到了符合要求的最长子序列，输出其长度；否则输出-1
    cout << res << endl;
}

python

# 定义一个常量N用于表示最大序列长度
N = 210
pre = [0] * N  # pre数组用于存储前缀和
n = 0          # 计数输入序列的长度

# 读取输入序列并转换为整数列表
input_sequence = input().split(',')  # 以逗号分隔输入
sequence = list(map(int, input_sequence))  # 将字符串转为整数列表

# 计算前缀和数组
for i in range(1, len(sequence) + 1):
    n += 1  # 序列长度+1
    pre[n] = pre[n - 1] + sequence[i - 1]  # 更新前缀和

# 读取目标和
sum_value = int(input())

res = -1  # 初始化结果为-1，表示没有符合条件的子序列

# 枚举所有区间[i, j]
for i in range(1, n + 1):  # 枚举区间起点i
    for j in range(i, n + 1):  # 枚举区间终点j
        # 计算区间[i, j]的和，并检查是否等于sum_value
        if pre[j] - pre[i - 1] == sum_value:
            # 更新结果为当前区间的长度
            res = max(res, j - i + 1)

# 输出最终结果
print(res)

java

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int target = Integer.parseInt(sc.nextLine());
 
        System.out.println(findMaxLen(nums, target));
    }
 
    public static int findMaxLen(int[] nums, int target) {
        int n = nums.length;
 
        // 前缀和数组
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
 
        // 记录最长连续子序列的长度
        int maxLen = -1;
 
        // 求解所有连续子序列的区间和
        for (int left = 1; left <= n; left++) {
            for (int right = left; right <= n; right++) {
                if (sum[right] - sum[left - 1] == target) {
                    maxLen = Math.max(maxLen, right - left + 1);
                }
            }
        }
 
        return maxLen;
    }
}

题目内容

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

样例2

输入

1,2,3,4,2
20

输出

-1

说明

没有满足要求的子序列，返回$-1$