最长连续子序列

题目描述

有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

题解

Python

# 滑动窗口
def main():
    nums = list(map(int, input().split(",")))
    expected_sum = int(input())
    assert 1 <= len(nums) <= 200
    assert 1 <= expected_sum

    # 最长子序的长度
    subarray_max_len = -1
    # 用于控制窗口左侧两侧的位置
    left = 0
    right = 0
    # 计算当前子序列的和
    current_sum = 0

    while left <= right and right < len(nums):
        if current_sum < expected_sum:
            # 子序列的和太小, 将窗口右侧向右移
            current_sum += nums[right]
            right += 1
        elif current_sum == expected_sum:
            # 和相等, 计算当前的子序列长度
            current_length = right - left
            subarray_max_len = max(subarray_max_len, current_length)
            current_sum += nums[right]
            right += 1
        else:
            # 子序列的和太大, 将窗口左侧向右移
            current_sum -= nums[left]
            left += 1

    print(subarray_max_len)


if __name__ == "__main__":
    main()

Rust

#![allow(unused)]
fn main() {
use std::cmp::Ordering;
use std::io::{stdin, BufRead};

// 滑动窗口
fn solution() {
    // 读取输入
    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let nums: Vec<i32> = line.trim().split(',').map(|x| x.parse().unwrap()).collect();

    line.clear();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let expected_sum: i32 = line.trim().parse().unwrap();

    // 最长子序的长度
    let mut subarray_max_len: usize = 0;
    // 用于控制窗口左侧两侧的位置
    let mut left: usize = 0;
    let mut right: usize = 0;
    // 计算当前子序列的和
    let mut current_sum: i32 = 0;

    while left <= right && right < nums.len() {
        match current_sum.cmp(&expected_sum) {
            Ordering::Less => {
                // 子序列的和太小, 将窗口右侧向右移
                current_sum += nums[right];
                right += 1;
            }
            Ordering::Equal => {
                // 和相等, 计算当前的子序列长度
                let current_length = right - left;
                subarray_max_len = subarray_max_len.max(current_length);
                // 并把窗口右侧向右移
                current_sum += nums[right];
                right += 1;
            }
            Ordering::Greater => {
                // 子序列的和太大, 将窗口左侧向右移
                current_sum -= nums[left];
                left += 1;
            }
        }
    }

    // 打印结果
    println!("{subarray_max_len}");
}
}

C++

#include <cassert>

#include <iostream>
#include <sstream>
#include <string>
#include <vector>

// 滑动窗口
void solution() {
  // 读取输入
  std::string line;
  std::cin >> line;
  std::stringstream ss(line);
  std::string part;
  std::vector<int> nums;
  while (std::getline(ss, part, ',')) {
    const int num = std::stoi(part);
    nums.push_back(num);
  }
  assert(1 <= nums.size() && nums.size() <= 200);

  int expected_sum;
  std::cin >> expected_sum;
  assert(1 <= expected_sum);

  // 最长子序的长度
  int subarray_max_len = -1;
  // 用于控制窗口左侧两侧的位置
  int left = 0;
  int right = 0;
  // 计算当前子序列的和
  int current_sum = 0;
  while (left <= right && right < nums.size()) {
    if (current_sum < expected_sum) {
      // 子序列的和太小, 将窗口右侧向右移
      current_sum += nums[right];
      right += 1;
    } else if (current_sum == expected_sum) {
      // 和相等, 计算当前的子序列长度
      const int current_length = right - left;
      subarray_max_len = std::max(subarray_max_len, current_length);
      current_sum += nums[right];
      right += 1;
    } else {
      // 子序列的和太大, 将窗口左侧向右移
      current_sum -= nums[left];
      left += 1;
    }
  }

  // 打印结果
  std::cout << subarray_max_len << std::endl;
}