algorithm - O(n) 算法，找到丢失的整数

Question

数组 A 包含 [0, n-1] 范围内的 n-1 个唯一整数，也就是说，这个范围内有一个数字不在 A 中。设计一个 O(n) 算法来找到该数字.除了数组 A 本身之外，只允许使用 O(1) 的额外空间。

这个问题需要一些帮助，

Answer 1

1. 对数组求和。
2. 计算 expected sum using arithmetic progression formula

给定这些值:一个是 0 + 1 + 2 + ... + n-1，另一个是您的实际元素的总和 - 想想它们之间有何不同，是什么一个有另一个没有。确保你知道，答案很简单。

编辑:(理论评论):
请注意，sum(array) 需要 2*log_2(max(arr)) 位。所以，如果你的元素都是 32 位整数，你最多需要 64 位来表示总和。
从纯粹的理论方法来看——它不是O(1)。但是，您可以使用数组本身(它包含超过 2*log_2(max(arr)) 位)来存储总和。