华为OD机试真题——查找接口成功率最优时间段（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现-海口c网

服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，数组中每个元素都是单位时间内失败率数值，数组中的数值为0~100的整数。给定一个数值minAverageLost表示某个时间段内平均失败率容忍值（即平均失败率需小于等于该值），要求找出数组中满足条件的最长时间段，若未找到则返回NULL。

输入描述：

第一行为minAverageLost。
第二行为数组，元素通过空格分隔。
minAverageLost及数组元素取值范围为0~100的整数，数组长度不超过100。

输出描述：

输出所有满足条件的最长时间段下标对，格式为{beginIndex}-{endIndex}（下标从0开始）。
若存在多个相同长度的最优时间段，按起始下标从小到大排序，并用空格拼接。

用例：

输入：
```
1  
0 1 2 3 4  
```
输出：
```
0-2  
```
说明：前3个元素的平均值为1，满足条件。
输入：
```
2  
0 0 100 2 2 99 0 2  
```
输出：
```
0-1 3-4 6-7  
```
说明：下标0-1、3-4、6-7对应的子数组平均值均≤2，且均为最长时段。

Java

问题分析

我们需要找到数组中所有满足平均失败率小于等于给定值的最长连续子数组，并输出这些子数组的起始和结束下标。如果有多个相同长度的子数组，按起始下标升序排列。

解题思路

转换数组：将每个元素减去给定的平均失败率，问题转化为寻找子数组的和小于等于0的最长长度。
前缀和数组：计算转换后数组的前缀和，便于快速计算子数组的和。
遍历所有可能的子数组：对于每个可能的结束下标，遍历所有可能的起始下标，记录满足条件的最长子数组。
收集结果：记录所有最长的子数组，按起始下标排序后输出。

代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int minAverageLost = Integer.parseInt(scanner.nextLine());String[] parts = scanner.nextLine().split(" ");int[] nums = new int[parts.length];for (int i = 0; i < parts.length; i++) {nums[i] = Integer.parseInt(parts[i]);}// 转换为每个元素减去minAverageLost的数组int[] b = new int[nums.length];for (int i = 0; i < nums.length; i++) {b[i] = nums[i] - minAverageLost;}// 计算前缀和数组int[] prefixSum = new int[b.length + 1];for (int i = 0; i < b.length; i++) {prefixSum[i + 1] = prefixSum[i] + b[i];}int maxLen = 0;List<int[]> result = new ArrayList<>();// 遍历所有可能的结束下标jfor (int j = 0; j < b.length; j++) {// 遍历所有可能的起始下标ifor (int i = 0; i <= j; i++) {// 检查子数组i到j的和是否<=0if (prefixSum[j + 1] <= prefixSum[i]) {int currentLen = j - i + 1;if (currentLen > maxLen) {maxLen = currentLen;result.clear();result.add(new int[]{i, j});} else if (currentLen == maxLen) {result.add(new int[]{i, j});}}}}if (maxLen == 0) {System.out.println("NULL");return;}// 按起始下标排序Collections.sort(result, (a, bArr) -> {if (a[0] != bArr[0]) {return a[0] - bArr[0];} else {return a[1] - bArr[1];}});// 使用LinkedHashSet去重并保持顺序LinkedHashSet<String> seen = new LinkedHashSet<>();for (int[] interval : result) {seen.add(interval[0] + "-" + interval[1]);}// 输出结果System.out.println(String.join(" ", seen));}
}

代码详细解析

输入处理：读取输入的平均失败率和数组。
数组转换：将每个元素减去平均失败率，转换为新数组b。
前缀和计算：构建前缀和数组prefixSum，用于快速计算子数组的和。
遍历子数组：双重循环遍历所有可能的起始和结束下标，检查子数组的和是否满足条件。
记录最长子数组：动态更新最长长度，并记录所有符合条件的子数组。
结果排序与去重：按起始下标排序，使用LinkedHashSet去重并保持顺序。
输出结果：拼接结果字符串并输出。

示例测试

示例1输入：

1  
0 1 2 3 4

输出：

0-2

示例2输入：

2  
0 0 100 2 2 99 0 2

输出：

0-1 3-4 6-7

示例3输入：

3  
1 1 1

输出：

0-2

综合分析

时间复杂度：O(n²)，遍历所有可能的子数组，适用于数组长度较小的情况（n ≤ 100）。
空间复杂度：O(n)，存储前缀和数组和结果列表。
优势：利用前缀和数组快速计算子数组的和，确保正确性和效率。
适用场景：适用于需要查找连续子数组满足特定条件的场景，如平均值、和等限制。

python

问题分析

我们需要找到数组中所有满足平均失败率 ≤ 给定值的最长连续子数组，并输出这些子数组的起始和结束下标。如果有多个相同长度的子数组，按起始下标升序排列。

解题思路

数学转换：
将问题转换为：寻找子数组的和 ≤ 0 的最长连续区间（原数组每个元素减去平均值后的新数组）。
前缀和数组：
计算新数组的前缀和，利用前缀和快速判断子数组的和是否 ≤ 0。
暴力遍历：
遍历所有可能的子数组，记录满足条件的最长区间。
结果处理：
去重并排序结果，按指定格式输出。

代码实现

def main():import sysinput = sys.stdin.read().splitlines()min_avg = int(input[0].strip())  # 读取容忍值arr = list(map(int, input[1].strip().split()))  # 读取失败率数组# 转换为差值数组（元素 - 容忍值）diff = [num - min_avg for num in arr]n = len(diff)# 计算前缀和数组（多一位方便计算）prefix = [0] * (n + 1)for i in range(n):prefix[i+1] = prefix[i] + diff[i]max_len = 0result = []# 遍历所有可能的子数组for end in range(n):for start in range(end + 1):# 子数组和是否 <= 0（prefix[end+1] <= prefix[start]）if prefix[end+1] <= prefix[start]:current_len = end - start + 1if current_len > max_len:max_len = current_lenresult = [(start, end)]elif current_len == max_len:result.append((start, end))if max_len == 0:print("NULL")return# 去重并排序（起始下标升序）unique = sorted(list(set(result)), key=lambda x: (x[0], x[1]))# 格式化输出output = ' '.join([f"{s