华为OD机试真题——最小循环子数组 （2025B卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 B卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《最小循环子数组》：

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

题目名称：最小循环子数组

知识点：字符串匹配、KMP算法（或枚举验证）
时间限制：1秒
空间限制：256MB
限定语言：不限

题目描述

给定一个由若干整数组成的数组 nums，请检查数组是否是由某个子数组重复循环拼接而成，并输出这个最小的子数组。

输入描述：

• 第一行输入数组中元素个数 n，1 ≤ n ≤ 100000。
• 第二行输入数组的数字序列 nums，以空格分割，0 ≤ nums[i] ≤ 10。

输出描述：
输出最小的子数组的数字序列，以空格分割。

备注：
数组本身是其最大的子数组，循环1次可生成自身。

示例：
输入：

9 1 2 1 1 2 1 1 2 1 

输出：

1 2 1 

说明：数组 [1,2,1,1,2,1,1,2,1] 可由子数组 [1,2,1] 重复循环3次拼接而成。

Java

问题分析

我们需要找到一个数组的最小循环子数组，即该数组可以由该子数组重复拼接而成。解决此问题的关键在于确定数组是否由某个子数组重复构成，并找出最小的这样的子数组。

解题思路

1. 候选子数组长度的确定：循环子数组的长度必须是原数组长度的因数。
2. 因数枚举：找出原数组长度的所有因数，并按从小到大顺序检查。
3. 循环验证：对于每个候选长度，验证数组是否可以由该长度的子数组重复构成。
4. 输出结果：找到第一个满足条件的最小子数组。

代码实现

import java.util.Scanner;import java.util.TreeSet;public class Main {  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 读取数组长度 int[] nums = new int[n]; for (int i = 0; i < n; i++) {  nums[i] = scanner.nextInt(); // 读取数组元素 } // 生成所有可能的因数（包括n） TreeSet<Integer> factors = new TreeSet<>(); for (int i = 1; i * i <= n; i++) {  if (n % i == 0) {  factors.add(i); factors.add(n / i); } } // 遍历所有因数，从小到大检查 for (int d : factors) {  if (check(nums, d)) {  // 验证当前因数对应的子数组是否符合循环条件 printResult(nums, d); // 打印结果 return; } } printResult(nums, n); // 最终必能匹配自身（d=n） } private static boolean check(int[] nums, int d) {  for (int i = 0; i < nums.length; i++) {  if (nums[i] != nums[i % d]) {  // 核心验证逻辑：每个位置必须与子数组对应位置相同 return false; } } return true; } private static void printResult(int[] nums, int d) {  StringBuilder sb = new StringBuilder(); for (int i = 0; i < d; i++) {  sb.append(nums[i]); if (i != d - 1) {  sb.append(\" \"); } } System.out.println(sb); }}

代码解析

1. 输入处理

   int n = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {  nums[i] = scanner.nextInt();}

   • 读取数组长度和元素。

2. 因数生成

   TreeSet<Integer> factors = new TreeSet<>();for (int i = 1; i * i <= n; i++) {  if (n % i == 0) {  factors.add(i); factors.add(n / i); }}

   • 遍历1到sqrt(n)，收集所有因数并存入有序集合，自动去重并排序。

3. 循环验证

   for (int d : factors) {  if (check(nums, d)) {  printResult(nums, d); return; }}

   • 从小到大遍历因数，验证每个因数对应的子数组是否符合循环条件。

4. 验证逻辑

   private static boolean check(int[] nums, int d) {  for (int i = 0; i < nums.length; i++) {  if (nums[i] != nums[i % d]) {  return false; } } return true;}

   • 核心逻辑：数组的每个元素必须等于其对应子数组位置的元素。

5. 结果输出

   private static void printResult(int[] nums, int d) {  StringBuilder sb = new StringBuilder(); for (int i = 0; i < d; i++) {  sb.append(nums[i]); if (i != d