关于LeetCode 448题JavaScript解法时间复杂度的疑问

解法代码 #

var findDisappearedNumbers = function(nums) {
    
    const numberSet = new Set();

    for(let i = 1; i < nums.length + 1; i++) {
        numberSet.add(i);
    }

    nums.forEach((element) => {
        if(numberSet.has(element)) {
            numberSet.delete(element);
        }
    });

    return Array.from(numberSet);
};

时间复杂度疑惑 #

上述解法的时间复杂度被认定为O(n)，但存在疑惑：解法先通过for循环填充numberSet，再通过forEach遍历nums检查并删除集合中的元素，两次遍历的时间复杂度均为O(n)，为何整体时间复杂度不是O(n²)？

解答 #

核心原因在于JavaScript中Set的add、has、delete操作的平均时间复杂度都是O(1)，而非O(n)。

• 第一个for循环：循环n次，每次执行numberSet.add(i)，单次操作耗时O(1)，这部分总时间为O(n)。
• 第二个forEach遍历：遍历n个元素，每次执行的numberSet.has(element)和numberSet.delete(element)都是O(1)操作，这部分总时间同样是O(n)。

将两部分时间相加，整体时间复杂度为O(n) + O(n) = O(n)，而非O(n²)。只有当集合的查找、删除操作是O(n)时，两次遍历才会导致O(n²)的复杂度，但Set的底层基于哈希表实现，保证了这些操作的高效性。

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