goden1704

面试题 17.04.消失的数字

1. 题目描述

数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

注意： 本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

标签 位运算 数组 哈希表 数学 排序

2. 解题

1. 用哈希表

2. 先求出sum(0, n), 再依次减去nums中的数字，剩下的就是缺少的数字

3. 位运算

位运算常见技巧

https://blog.csdn.net/wat1r/article/details/114298873?spm=1001.2014.3001.5501