哈希表求解数组缺失数字问题及多缺失值处理方案咨询

你的代码存在3个核心问题，导致if判断永远无法触发：

• enumerate(nums)的返回值顺序搞反了，正确返回顺序是(索引, 数组元素值)，你写反了两个变量的位置，导致字典存入的键值逻辑完全错误
• 只有出现过的数字才会被作为键存入defaultdict，你遍历d.items()的时候所有键都是已出现的数字，自然不可能出现len(v)==0的情况，所以这个判断永远不会生效
• 你已经用求和公式算出了缺失值，和哈希表遍历的逻辑完全脱节，属于冗余逻辑

如果要坚持用哈希表思路实现需求，修复后的代码如下：

from collections import defaultdict
class Solution(object):
    def missingNumber(self, nums):
        d = defaultdict(bool)
        n = len(nums)
        # 存储所有出现过的数字
        for num in nums:
            d[num] = True
        # 遍历[0,n]区间找未出现的数字
        for i in range(n+1):
            if not d.get(i, False):
                return i

如果不需要刻意用哈希表，本题最优解是直接用求和公式，时间复杂度O(n)、空间复杂度O(1)，不需要额外存储结构：

class Solution(object):
    def missingNumber(self, nums):
        n = len(nums)
        return n*(n+1)//2 - sum(nums)

入门阶段优先掌握两种最优思路即可：

• 思路1：哈希集合法（理解成本最低，实现最简单）
  时间复杂度O(m)（m为区间最大值），空间复杂度O(n)（n为数组长度）
  实现步骤：
  1. 把数组所有元素存入哈希集合
  2. 遍历题目给定的取值区间，把所有不在集合里的数收集起来，就是所有缺失值
     比如示例输入[0,1,2,6,8]，如果取值范围是[0,8]，遍历时会直接收集到3、4、5、7四个缺失值
• 思路2：原地交换法（空间最优，无额外存储开销）
  时间复杂度O(n)，空间复杂度O(1)
  实现逻辑：把每个数字交换到它对应下标的位置，比如数字3就放到下标3的位置，全部交换完成后遍历数组，下标和元素值不相等的位置就是缺失的数字，如果区间最大值超过数组长度，超出范围的未匹配值也属于缺失值。

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