无序等差数列缺失项查找JS代码执行超时如何优化

你在完成Code Wars平台的《Missing number in Unordered Arithmetic Progression》编程挑战，题目规则如下：

• 等差数列（Arithmetic Progression）指相邻连续项差值为固定常数的数列
• 给定输入是原等差数列打乱顺序后的集合，恰好缺失原序列中的1个项，其余项和原AP完全一致，需要求解这个缺失项
• 输入为无序序列，需要适配超大规模元素数量的输入，满足执行时间限制
• 题目保证不会出现原序列最小值或最大值缺失的场景，例如[4, 6, 3, 5, 2]缺失1或7的用例不会出现在测试中

示例：

find([3, 9, 1, 11, 13, 5]) # 返回值7

你当前的实现如下，可通过99%测试用例，但大规模随机用例会超时：

function find(seq) {
    function compareNumbers(a, b) {
        return a - b;
    }
    let arr = [...seq].sort(compareNumbers);
    let difference = arr[1]-arr[0];
    let arrLen = arr.length;
    let i=0;
    while(i<arrLen){
        if(arr[i+1]-arr[i]!==difference) return arr[i] + difference;
        i++;
    }
}

超时核心原因：所有基于排序的实现（包括JS内置sort、你自行尝试实现的快速排序）时间复杂度都是O(nlogn)，当输入规模达到10^5甚至更高量级时，运算耗时会远超时间限制。且JS内置sort是引擎层面深度优化的排序实现，性能普遍高于手写的普通快排，不管怎么优化排序逻辑或者后续遍历逻辑，都无法突破复杂度瓶颈，必然会在超大规模输入下超时。

利用题目给出的「最小值、最大值不会缺失」的条件，完全不需要排序，通过等差数列数学性质直接计算结果：

1. 遍历一次输入序列，拿到三个值：序列最小值min、序列最大值max、序列所有元素的和currentSum
2. 原等差数列的总项数为seq.length + 1（因为只缺了1个元素），结合等差数列求和公式，原序列完整总和为expectedSum = (min + max) * (seq.length + 1) / 2
3. 原总和和当前输入序列和的差值，就是缺失的项：missingNum = expectedSum - currentSum

优化后的JS实现代码：

function find(seq) {
    let min = Infinity;
    let max = -Infinity;
    let sum = 0;
    const len = seq.length;
    for (let i = 0; i < len; i++) {
        const num = seq[i];
        if (num < min) min = num;
        if (num > max) max = num;
        sum += num;
    }
    const expectedSum = (min + max) * (len + 1) / 2;
    return expectedSum - sum;
}

该实现时间复杂度为O(n)，空间复杂度为O(1)，没有额外的数组拷贝、排序开销，即使输入规模达到百万级也可以在极短时间内完成计算，完全满足时间限制要求。

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