这段LeetCode从排列构建数组的代码空间复杂度是O(1)还是O(N)？是否符合要求？

问题背景 #

这是一道LeetCode题目，要求从排列构建数组，核心挑战是使用**O(1)**空间复杂度完成求解。以下是给出的解决方案代码：

var buildArray = function(nums) {
        let len = nums.length
        for (let i = 0; i < len; i++) {
           nums.push(nums[nums[i]]); 
        }
        nums = nums.splice(len, nums.length);
        return nums;
    };

疑问解答 #

1. 该解决方案是否符合O(1)空间复杂度要求？ #

不符合。这段代码通过nums.push()向原数组追加了N个元素（N为原数组的初始长度），后续用splice截取这部分元素作为结果返回。虽然没有额外声明新的数组变量，但原数组被扩展了一倍长度，新增的N个元素占用了**O(N)**级别的额外空间，因此整体空间复杂度是O(N)，不满足题目要求的O(1)空间复杂度。

2. 操作原数组但通过在末尾追加元素增加其长度，是否意味着分配了新空间，从而导致空间复杂度为O(N)？ #

是的。数组在底层一般是连续的内存块存储，当原数组的预留内存不足以容纳新元素时，追加操作会触发内存重新分配——系统会开辟一块更大的连续内存区域，将原数组内容复制过去，再存储新增元素。这部分新增的N个元素需要的内存空间是O(N)级别的，属于算法执行过程中使用的额外空间，因此会导致整体空间复杂度变为O(N)。

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