【最新华为OD机试E卷】最长连续子序列(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目敬请期待

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🍰 最长连续子序列

问题描述

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

输入格式

输入包含两行：

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

输出格式

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

样例输入

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