LeetCode最长连续序列算法的时间复杂度是否为O(n)？

针对LeetCode的「最长连续序列」问题，有如下JavaScript解法：

var longestConsecutive = function(nums) {
  if (nums == null || nums.length === 0) return 0;
  const set = new Set(nums);
  let longest = 0;
  for (let num of nums) {
    if (!set.has(num - 1)) {
      let count = 0;
      while (set.has(count+num)) {
        count++;
      }
      longest = Math.max(longest,count);
    }
  }
  return longest;
};

有人质疑这个解法因存在嵌套循环，时间复杂度不是O(n)，但它却能满足题目O(n)的约束并通过测试，其实这个算法的时间复杂度确实是O(n)，原因如下：

• 外层循环遍历数组每一个元素，但仅当当前元素是连续序列的起点（即num-1不在集合中）时，才会触发内层while循环。
• 每个元素只会被内层循环处理一次：比如连续序列[1,2,3,4]，只有遍历到1时才会进入内层循环，依次检查1、2、3、4；而遍历2、3、4时，因num-1存在于集合中，不会触发内层循环。整个算法执行过程中，所有元素被内层循环访问的总次数恰好等于数组长度n，外层循环总次数也是n，因此总操作次数为O(n)。
• 评论的误区在于只看到嵌套循环结构，忽略了内层循环的触发条件限制，实际上不会出现O(n²)级别的重复遍历。

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