Java中如何比较两个循环数组的元素是否为相同序列

判断两个循环数组是否属于相同元素序列，核心逻辑是验证其中一个数组的所有循环移位结果中，是否存在和另一个数组完全匹配的情况。

前置校验 #

首先处理边界场景，只要满足以下任意一种情况就可以直接返回结果：

• 两个数组其中一个为null：仅当二者都为null时返回true，否则返回false
• 两个数组长度不一致：直接返回false
• 两个数组长度都为0：返回true

基础实现（暴力匹配，O(1)额外内存） #

不需要额外申请数组空间，通过取模运算模拟循环数组的访问，逐个匹配所有可能的移位场景：

import java.util.Objects;

public class CircularArrayMatcher {
    public static <T> boolean isCircularEqual(T[] arr1, T[] arr2) {
        // 前置校验
        if (arr1 == null || arr2 == null) return arr1 == arr2;
        if (arr1.length != arr2.length) return false;
        int len = arr1.length;
        if (len == 0) return true;

        // 遍历所有可能的起始偏移量
        offsetLoop:
        for (int offset = 0; offset < len; offset++) {
            for (int idx = 0; idx < len; idx++) {
                // 用取模模拟循环访问
                T elem1 = arr1[(offset + idx) % len];
                T elem2 = arr2[idx];
                if (!Objects.equals(elem1, elem2)) {
                    continue offsetLoop;
                }
            }
            // 所有元素匹配成功
            return true;
        }
        return false;
    }

    // 测试示例
    public static void main(String[] args) {
        Character[] arrA = {'A','B','C','D','E','F'};
        Character[] arrB = {'D','E','F','A','B','C'};
        Character[] arrC = {'D','F','E','A','B','C'};
        
        System.out.println(isCircularEqual(arrA, arrB)); // 输出 true
        System.out.println(isCircularEqual(arrA, arrC)); // 输出 false
    }
}

注意：如果数组元素是自定义类，需要确保正确重写了equals()方法，否则对象引用比较会导致结果不符合预期。如果是基本类型数组，可以重载方法直接用==比较元素，不需要Objects.equals。

优化实现（KMP算法，O(n)时间复杂度） #

如果数组长度较大，暴力匹配的O(n²)时间复杂度性能不足，可以将第一个数组拼接成长度为2倍的新数组，再用KMP算法匹配第二个数组是否为该拼接数组的连续子串，整体时间复杂度可以降到O(n)，适合大数组场景：

import java.util.Arrays;
import java.util.Objects;

public static <T> boolean isCircularEqualKmp(T[] arr1, T[] arr2) {
    if (arr1 == null || arr2 == null) return arr1 == arr2;
    if (arr1.length != arr2.length) return false;
    int len = arr1.length;
    if (len == 0) return true;

    // 拼接arr1得到两倍长度的数组
    T[] doubled = Arrays.copyOf(arr1, len * 2);
    System.arraycopy(arr1, 0, doubled, len, len);
    
    // 调用KMP匹配逻辑，判断arr2是否是doubled的连续子数组即可
    return kmpSearch(doubled, arr2) != -1;
}

// KMP匹配实现，返回匹配的起始下标，无匹配返回-1
private static <T> int kmpSearch(T[] text, T[] pattern) {
    int[] lps = buildLps(pattern);
    int textIdx = 0, patternIdx = 0;
    while (textIdx < text.length) {
        if (Objects.equals(text[textIdx], pattern[patternIdx])) {
            textIdx++;
            patternIdx++;
            if (patternIdx == pattern.length) {
                return textIdx - patternIdx;
            }
        } else if (patternIdx > 0) {
            patternIdx = lps[patternIdx - 1];
        } else {
            textIdx++;
        }
    }
    return -1;
}

// 构建KMP的最长公共前后缀数组
private static <T> int[] buildLps(T[] pattern) {
    int[] lps = new int[pattern.length];
    int len = 0;
    int idx = 1;
    while (idx < pattern.length) {
        if (Objects.equals(pattern[idx], pattern[len])) {
            len++;
            lps[idx] = len;
            idx++;
        } else if (len > 0) {
            len = lps[len - 1];
        } else {
            lps[idx] = 0;
            idx++;
        }
    }
    return lps;
}

内容的提问来源于stack exchange，提问作者mohamad yassine