华为 · 数论 · 算法编程题
华为 数论 N ≤ 1e6 时限 5 秒 / 256 MB

题目描述

在一项对时空连续体的高维研究中,科学家们发现了一种被称为“零点能量共振”的现象。
这种现象表现为在一段连续的时间序列能量读数中,存在一个可以被精确分割成两个连续部分、且每个部分的能量扰动总和都恰好为零的区间。
这种特殊的“对称”共振区间被认为是时空稳定的关键指标。
给定一个记录了 N 个连续时间点能量扰动值的数组 A 。
数组中的元素为带符号整数。
你的任务是找出其中最短的、能够表现出“零点能量共振”的子数组。
一个子数组被称为“可对称分割”,如果它能被分割成两个连续的子数组,且这两个子数组的元素和都为零。
形式化地说,对于一个子数组 A[i ... j-1] (下标从 i 到 j-1 ),如果存在一个分割点 k (其中 i < k < j ),使得:
Σ_p=i^k-1 A[p] = 0 并且 Σ_p=k^j-1 A[p] = 0
那么,这个子数组 A[i ... j-1] 就是一个满足条件的共振区间。
你的目标是找到所有这类共振区间中,长度最短的一个或多个。
你需要报告这个最短的长度,以及具有该最短长度的共振区间的数量。

输入输出

输入描述
输入包含两行:
第一行是一个整数 N ,代表时间序列的长度(数组 A 的元素数量)。
1 ≤ N ≤ 10^6
第二行包含 N 个整数 X_i ,代表数组 A 的元素。
-10000 ≤ X_i ≤ 10000
输出描述
输出一行,包含两个整数,由空格隔开:
1. 满足条件的最短子数组的长度。
2. 具有该最短长度的子数组的个数。
如果不存在任何满足条件的子数组,则输出 `-1 -1`。

样例共 3 组

样例 1
输入
5
1 -1 1 -1 1
输出
4 2
样例 2
输入
7
0 100 1 300 2 10 0
输出
-1 -1
样例 3
输入
7
100 1 -1 3 -2 -1 100
输出
5 1

算法解析依据一般

考点:数论

数据规模 N ≤ 1e6 | 限制 5 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 1e6
  • 元素值域:X_i ≤ 1e4(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
  • 源站时限:5 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:数论

围绕整除、质因数、同余的经典结论与筛法。

思路框架(数论 通法 · 非本题专属)

  1. 先做质因数分解(试除到 √n,或预处理筛出 1e6 内质数)。
  2. 按题意套结论:约数个数 = Π(e_i+1);gcd / lcm 用辗转相除法。
  3. 涉及大数取模时,每一步运算后都取模,避免溢出。
  4. 需要区间内质数时用埃氏筛 / 线性筛。

实现要点:模运算规律:(a+b)%m = ((a%m)+(b%m))%m,乘法则同理;减法要 +m 防止负数。

复杂度:时间 O(√n) 分解 / O(n log log n) 筛 | 空间 O(n) 筛表

该范式的通法易错点

  • 取模后相减为负数没处理。
  • a*b 在取模前就溢出了。

对照本题

  • 数据规模 N ≤ 1e6,只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:5 / 1 -1 1 -1 1
  • 输出:4 2

样例 2

  • 输入:7 / 0 100 1 300 2 10 0
  • 输出:-1 -1

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-11月19号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解