华为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