不排序、无额外O(n)空间判断两个无序数组是否相等

嘿，这个问题问得好——这是个典型的存在权衡的问题，你说得对，求和法确实不可靠（你举的[4,2]和[1,5]的反例正好说明了这点）。咱们来拆解一下如何在不使用O(n)额外空间、也不排序原数组的前提下解决这个问题。

不管用什么方法，第一步一定要先判断两个数组的长度是否相等。如果长度不一样，直接返回false就行——连元素数量都不同，肯定不可能等价。

方法1：双重循环+频率校验（O(n²)时间，O(1)空间） #

这是最贴合你需求的解法：完全不修改原数组，也不用额外的大空间，只用几个临时变量。核心逻辑是：对数组A中的每个元素，统计它在A和B中的出现次数，只要有一个元素的次数不匹配，就说明数组不等价。

为了避免重复统计同一个元素（比如A里有多个相同的元素，每次遍历到都重复统计一遍），可以在遍历A的时候，跳过已经检查过的元素——比如当遍历到A[i]时，先看看前面有没有和它相同的元素，如果有，就直接跳过，不用再统计了。

举个Java代码的例子：

public static boolean areArraysEquivalent(int[] A, int[] B) {
    if (A.length != B.length) return false;
    int n = A.length;

    for (int i = 0; i < n; i++) {
        // 跳过已经检查过的重复元素
        boolean alreadyChecked = false;
        for (int j = 0; j < i; j++) {
            if (A[j] == A[i]) {
                alreadyChecked = true;
                break;
            }
        }
        if (alreadyChecked) continue;

        // 统计当前元素在A和B中的出现次数
        int countInA = 0, countInB = 0;
        for (int num : A) {
            if (num == A[i]) countInA++;
        }
        for (int num : B) {
            if (num == A[i]) countInB++;
        }

        if (countInA != countInB) return false;
    }
    return true;
}

这个方法的空间复杂度是严格的O(1)，但时间复杂度是O(n²)，所以更适合小规模数组的场景。

方法2：原地排序后比对（O(n log n)时间，O(1)空间，但会修改原数组） #

如果你的“不排序数组”只是指不想额外创建排序后的数组，而可以接受修改原数组的顺序，那这个方法效率更高：用原地排序算法（比如堆排序，它的空间复杂度是O(1)）对两个数组分别排序，然后逐个比对元素是否一致。

步骤很简单：

• 对数组A和B分别进行原地堆排序
• 遍历两个数组，逐一比较对应位置的元素，只要有一个位置元素不同，返回false
• 遍历完成后返回true

但要注意：这个方法会改变原数组的顺序，如果要求必须保留原数组的原始状态，那这个方法就不适用了。

你已经知道求和法不行，其实扩展到平方和、立方和这类方法也存在反例。比如[1,2,3,6]和[0,4,5,3]，它们的求和都是12，平方和都是50，但元素组成完全不同。所以这类基于数学累加的方法都有漏洞，绝对不能用来做判断。

• 如果必须完全不修改原数组且不能用O(n)额外空间，优先选双重循环频率校验法，虽然慢，但满足你的所有要求；
• 如果可以接受修改原数组，原地排序后比对的方法时间效率更高；
• 所有数学累加类的方法都存在错误风险，别用。

内容的提问来源于stack exchange，提问作者Atul Agrawal