javascript - 为什么我使用 1 个大小为 n 的数组的特定 JavaScript 算法总是比使用 3 个大小为 n 的数组的另一个算法消耗更多的内存？

Question

我正在查看 LeetCode 问题Product of Array except Self。我有一个 JS 解决方案，它使用一个大小为 n 的数组（n 是输入数组的长度），另一个非常相似，但使用了 3 个大小为 n 的数组。无论我提交多少次解决方案，1-array 解决方案似乎都比 3-array 解决方案使用更多的空间。（我说它使用“更多空间”，因为虽然实际差异只有几 MB，但百分位数差异很大 - 1-array 解决方案比大约 90-95% 的提交使用更多空间，而 3-array 解决方案比大约 50-60% 的提交使用更多的空间。）

我还有一个 2 阵列解决方案，就空间使用而言，它始终位于我的其他两个解决方案的中间。这是有道理的，但顺序是相反的——我希望 1-array 解决方案总是比 3-array 解决方案使用更少的空间。为了让事情变得更奇怪，我测试了别人的 1-array 解决方案，他们使用的空间比我的 1-array 解决方案少得多，但我不明白为什么。也许这是我不知道的 JS 的一个怪癖，或者我遗漏了一些明显的东西。任何输入将不胜感激！

以下是解决方案。实际的算法逻辑基本相同；主要区别在于他们使用了多少个数组。

3 数组解决方案（大小为 n 的 3 个数组分别为 left、right 和 res）：

const productExceptSelf = function(nums) {
    const left = [];
    const right = new Array(nums.length);

    for (let i = 0; i < nums.length; i++) {
        if (i === 0)
            left.push(1);
        else
            left.push( left[i - 1] * nums[i - 1] );
    }
    for (let i = nums.length - 1; i >= 0; i--) {
        if (i === nums.length - 1)
            right[i] = 1;
        else
            right[i] = right[i + 1] * nums[i + 1];
    }

    const res = [];
    for (let i = 0; i < nums.length; i++)
        res.push( left[i] * right[i] );

    return res;
};

1-array 解决方案（它使用与上述相同的逻辑，但使用大小为 n 的单个 res 数组）：

const productExceptSelf = function(nums) {
    const res = [ 1 ];

    for (let i = 1; i < nums.length; i++)
        res.push( res[i - 1] * nums[i - 1] );

    let right = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }

    return res;
};

其他人的 1-array 解决方案（我理解为什么它会比我的更快，因为它只使用 1 个循环，但我不明白为什么它会使用这么少的空间，因为 res 数组的大小也是 n）：

const productExceptSelf = function(nums) {
    const res = [];
    let leftMult = 1;
    let rightMult = 1;
    
    for (let i = nums.length - 1, j = 0; i >= 0; i--, j++) {
        res[i] = (res[i] ?? 1) * rightMult;
        res[j] = (res[j] ?? 1) * leftMult;
        
        rightMult *= nums[i];
        leftMult *= nums[j];
    }
    
    return res;
}

标签： javascriptarraysalgorithmmemory