O(n)的解法

看了一些题解都是hash或者排序、划分的解法，时间和空间复杂度都不满足要求。这里给一个时间复杂度O(n),空间复杂度O(1)的解法。
其实这个题目不太严谨，本质上是一个简单的数学问题。应该再加上一个条件：加上这个缺失的最小整数后，它是一个连续数组（不包括0）。
不知道是不是以为这个原因，很多朋友没有这么去想。

如果是连续数组，这个问题就简单多了：
我们先求出数组和，然后再计算出[min, max]连续区间的和。差值就是缺少的那个正数。
处理一下相等的情况就可以了。

class Solution {
public:
    /**
     * return the min number
     * @param arr int整型vector the array
     * @return int整型
     */
    int minNumberdisappered(vector<int>& arr) {
        int lmin = arr[0], lmax = arr[0];
        int sum1 = arr[0];
        for(int i = 1; i < arr.size(); i++) {
            if(lmin > arr[i]) lmin = arr[i];
            if(lmax < arr[i]) lmax = arr[i];
            sum1 += arr[i];
        }
        int sum2 = 0;
        for(int i = lmin; i <= lmax; i++) sum2 += i;
        int loss = sum2 - sum1 == 0 ? lmax+1 : sum2 - sum1;
        return max(1, loss);
    }
};