【华为OD-E卷 - 最长连续子序列 100分（python、java、c++、js、c）】

【华为OD-E卷 - 最长连续子序列 100分（python、java、c++、js、c）】

题目

有N个正整数组成的一个序列。给定整数sum，求长度最长的连续子序列，使他们的和等于sum，返回此子序列的长度，
如果没有满足要求的序列，返回-1

输入描述

• 第一行输入是：N个正整数组成的一个序列

第二行输入是：给定整数sum

输出描述

• 最长的连续子序列的长度

备注

• 输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分隔 序列长度：1 <= N <= 200 输入序列不考虑异常情况

用例

用例一：

输入：

1,2,3,4,2
6

输出：

3

用例二：

输入：

1,2,3,4,2
20

输出：

-1

python解法

• 解题思路：
• 本题目要求找出一个数组中，和为目标值 target 的最长子数组的长度。为了高效地解决问题，我们可以使用 前缀和（prefix sum）和 哈希表 来优化计算。

关键步骤：
前缀和：对于一个数组，前缀和是一个到当前位置为止的元素和，记录每一个元素到当前位置的和。通过前缀和的差值可以帮助我们找到和为目标值的子数组。
哈希表：使用哈希表 prefix_sum 来记录每个前缀和第一次出现的位置。若当前的前缀和减去目标值已经在哈希表中出现过，则表示从该位置到当前下标之间的子数组和为目标值。
步骤解析：
从头到尾遍历数组，维护一个累加的前缀和 current_sum。
对于每一个位置 i，计算 current_sum - target，如果它已经存在于 prefix_sum 哈希表中，说明从该位置到当前下标之间的子数组和等于目标值 target。
如果 current_sum 在哈希表中不存在，说明第一次遇到这个前缀和，将它与当前下标 i存入哈希表。
算法步骤：
初始化一个哈希表 prefix_sum，记录前缀和及其第一次出现的位置。我们假设前缀和为0的初始位置是 -1，这样便于处理从数组的开头就能达到目标值的情况。
遍历数组，计算每个位置的 current_sum。
如果 current_sum - target 存在于哈希表中，计算从该位置到当前下标的子数组长度，更新最大长度 max_len。
如果 current_sum 不在哈希表中，将其加入哈希表，记录当前下标。
时间复杂度：
时间复杂度为 O(n)，其中 n 是数组的长度。遍历数组一次，每次查找和更新哈希表的操作都是 O(1)。

# 输入数组nums和目标值target
nums = list(map(int, input().split(",")))  # 输入的数组，按逗号分隔
target = int(input())  # 目标和

# 主函数，返回和为target的最长子数组长度
def findMaxLength():
    # 使用哈希表记录前缀和及其出现的位置，初始时前缀和为0对应的位置是-1
    prefix_sum = {0: -1}
    current_sum = 0  # 当前的前缀和
    max_len = -1  # 记录最长子数组的长度，初始化为-1表示还未找到

    # 遍历数组nums
    for i in range(len(nums)):
        # 更新当前的前缀和
        current_sum += nums[i]
        
        # 如果current_sum - target在哈希表中，表示存在一个子数组和为target
        if current_sum - target in prefix_sum:
            # 更新最大长度
            max_len = max(max_len, i - prefix_sum[current_sum - target])
        
        # 如果current_sum未出现过，记录它的位置
        if current_sum not in prefix_sum:
            prefix_sum[current_sum] = i

    return max_len  # 返回找到的最大子数组长度

# 输出结果
print(findMaxLength())

java解法

• 解题思路
• 本题要求在给定的数组中，找到和为 targetSum 的最长子数组的长度。该问题本质上是寻找一个和为给定值的连续子数组，并返回其最大长度。我们可以通过暴力法（两层循环）来解决这个问题。

关键思路：
暴力法：我们可以通过两层循环来遍历数组的所有子数组。在外层循环中，我们固定子数组的起始位置 start，在内层循环中遍历从 start 到数组末尾的所有可能的子数组结尾位置 end，计算每个子数组的和。

条件判断：如果某个子数组的和等于 targetSum，就更新最大长度 maxLength。

时间复杂度：这种方法的时间复杂度为 O(n²)，其中 n 是数组的长度。因为我们对于每个可能的子数组，都要计算其和。

算法步骤：
输入处理：读取数组和目标值 targetSum。
解析输入：将输入的字符串分割并转换为整数数组。
暴力查找：通过两层循环，计算每个可能的子数组和，若等于目标值，更新最大长度。
返回结果：输出找到的最大长度

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 解析输入的数字序列
        int[] numbers = parseSequence(scanner.nextLine());
        // 读取目标和
        int sum = Integer.parseInt(scanner.nextLine());

        // 输出结果，调用findMaxSubarrayLength函数计算最大长度
        System.out.println(findMaxSubarrayLength(numbers, sum));
    }

    // 解析输入的数字序列，返回整数数组
    public static int[] parseSequence(String input) {
        String[] tokens = input.split(",");  // 以逗号为分隔符分割输入字符串
        int[] result = new int[tokens.length];  // 初始化整数数组
        for (int i = 0; i < tokens.length; i++) {
            result[i] = Integer.parseInt(tokens[i]);  // 将每个分割后的字符串转换为整数
        }
        return result;  // 返回解析后的数组
    }

    // 找到和为targetSum的最长子数组的长度
    public static int findMaxSubarrayLength(int[] numbers, int targetSum) {
        int maxLength = -1;  // 初始化最大长度，-1表示没有找到符合条件的子数组

        // 外层循环：遍历数组中的每个起始位置
        for (int start = 0; start < numbers.length; start++) {
            int currentSum = 0;  // 初始化当前子数组的和

            // 内层循环：遍历从start到数组末尾的每个结束位置
            for (int end = start; end < numbers.length; end++) {
                currentSum += numbers[end];  // 更新当前子数组的和

                // 如果当前子数组的和等于targetSum
                if (currentSum == targetSum) {
                    maxLength = Math.max(maxLength, end - start + 1);  // 更新最大子数组长度
                }
            }
        }

        return maxLength;  // 返回结果
    }
}

C++解法

• 解题思路

更新中

C解法

• 解题思路

• 该题的目标是寻找给定整数数组中和为指定 targetSum 的最长子数组的长度。为了高效地解决这个问题，我们采用了滑动窗口（Sliding Window）技巧，通过维持一个动态调整的窗口，避免使用暴力法（两层循环）来提高效率。

关键思路：
滑动窗口：我们通过两个指针 left 和 right 来维持一个“窗口”，窗口内的元素之和小于等于 targetSum。每次扩展窗口（即增加 right 指针），当当前窗口的和大于 targetSum 时，我们通过移动 left 指针来缩小窗口，直到当前窗口的和不大于 targetSum。

动态更新窗口：每次找到符合条件的窗口时，检查该窗口的大小是否是目前找到的最大值，并更新最大长度。

时间复杂度：这个方法的时间复杂度是 O(n)，其中 n 是数组的长度。通过滑动窗口技巧，left 和 right 每个指针最多只会遍历一次数组，因此时间复杂度为线性

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 解析输入的字符串，转换为整数数组，并返回数组的长度
int* parseInput(char* input, int* length) {
    char* token = strtok(input, ",");  // 使用strtok以逗号分隔字符串
    int* result = malloc(100 * sizeof(int));  // 分配一个较大的内存空间，假设最大输入为100个数
    int index = 0;

    // 遍历所有的token，将其转换为整数并存储到结果数组中
    while (token != NULL) {
        result[index++] = atoi(token);  // 使用atoi将字符串转换为整数
        token = strtok(NULL, ",");  // 获取下一个token
    }

    *length = index;  // 将数组的长度存入length中
    return result;  // 返回解析得到的整数数组
}

// 使用滑动窗口技术查找和为targetSum的最长子数组
int findLongestSubarray(int* nums, int length, int targetSum) {
    int maxLen = -1;  // 初始化最大长度为-1，表示如果没有找到子数组，则返回-1
    int currentSum = 0;  // 当前窗口的和
    int left = 0;  // 滑动窗口的左指针

    // 遍历数组，右指针从0到length-1
    for (int right = 0; right < length; right++) {
        currentSum += nums[right];  // 将当前元素加入到窗口中，更新当前和

        // 当当前窗口的和大于targetSum时，移动左指针缩小窗口
        while (currentSum > targetSum && left <= right) {
            currentSum -= nums[left++];  // 从窗口中移除左边的元素，并将左指针向右移动
        }

        // 如果当前窗口的和等于targetSum，更新最大长度
        if (currentSum == targetSum) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;  // 更新最大子数组长度
            }
        }
    }

    return maxLen;  // 返回最大子数组长度
}

int main() {
    char input[100];  // 用于存储输入的字符串
    fgets(input, sizeof(input), stdin);  // 读取输入字符串
    input[strcspn(input, "\n")] = 0;  // 去除末尾的换行符

    int length;  // 数组的长度
    int* nums = parseInput(input, &length);  // 解析输入并返回整数数组

    int targetSum;  // 目标和
    scanf("%d", &targetSum);  // 读取目标和

    // 调用findLongestSubarray函数计算结果并打印
    printf("%d\n", findLongestSubarray(nums, length, targetSum));

    free(nums);  // 释放动态分配的内存
    return 0;
}

JS解法

• 解题思路

• 本题的目标是找到一个整数数组中，和为给定 target 的最长连续子数组，并返回其长度。我们可以使用 前缀和（Prefix Sum） 和 哈希表（Map） 技巧来高效地求解这个问题。

关键思路：
前缀和（Prefix Sum）：
前缀和是指数组中某个位置之前（包括当前位置）的元素和。我们可以通过维护当前的前缀和来快速计算某一范围内的子数组的和。

哈希表（Map）：
我们使用哈希表来记录每个前缀和首次出现的位置。具体地，假设当前索引为 i，当前前缀和为 prefixSum，我们希望找到一个之前的索引 j 使得 prefixSum - sum 出现在哈希表中，这样就能得到一个和为 sum 的子数组。子数组的长度就是 i - j。

具体步骤：

初始化一个哈希表 prefixSumMap，用来存储每个前缀和首次出现的索引，最初将 prefixSumMap[0] = -1，表示如果当前前缀和等于目标和 sum，从 0 到当前位置就是一个合法的子数组。
遍历数组，计算当前的前缀和 prefixSum，并检查 prefixSum - target 是否已经出现在哈希表中。如果出现，则说明找到了一个和为 target 的子数组，更新最大子数组长度 maxLen。
最终返回最长子数组的长度。
时间复杂度：
时间复杂度为 O(n)，其中 n 是数组的长度。我们只遍历一次数组，并且每次操作哈希表的查询和更新都是常数时间 O(1)。
空间复杂度：
空间复杂度为 O(n)，用于存储哈希表

async function main() {
    const input = await getInput();  // 获取用户输入
    const nums = input[0].split(",").map(Number);  // 将第一个输入转为整数数组
    const target = Number(input[1]);  // 第二个输入是目标和

    // 输出最长子数组的长度
    console.log(findLongestSubsequence(nums, target));
}

// 获取输入的函数，返回一个包含两个输入的数组
function getInput() {
    return new Promise((resolve) => {
        const rl = require('readline').createInterface({ input: process.stdin });
        const inputs = [];  // 用来保存输入的数组
        rl.on('line', (line) => inputs.push(line))  // 逐行读取输入
          .on('close', () => resolve(inputs));  // 输入完成后返回输入数组
    });
}

// 查找和为target的最长连续子数组
function findLongestSubsequence(nums, sum) {
    const prefixSumMap = new Map();  // 用哈希表记录前缀和和其对应的索引
    prefixSumMap.set(0, -1);  // 初始前缀和为0，对应的索引为-1
    let maxLen = -1;  // 存储最长子数组的长度
    let prefixSum = 0;  // 当前前缀和

    // 遍历数组
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];  // 更新当前前缀和

        // 检查前缀和是否已经出现过，若出现过，说明存在一个和为target的子数组
        if (prefixSumMap.has(prefixSum - sum)) {
            // 更新最大子数组长度
            maxLen = Math.max(maxLen, i - prefixSumMap.get(prefixSum - sum));
        }

        // 如果当前前缀和没有出现过，记录当前前缀和的索引
        if (!prefixSumMap.has(prefixSum)) {
            prefixSumMap.set(prefixSum, i);
        }
    }

    return maxLen;  // 返回最长子数组的长度
}

main();  // 调用main函数，开始执行

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏