题解 | #缺失数字#

思路
方法1：利用等差数列递推公式

题目明确指出所给的数据在0~n之间，且所有数值均只出现一次，而对于数列求和有求和公式 ，
故，可以遍历整个数组求出总和sum1，再借助上述求和公式计算在不缺失数字的情况下的总和sum2，sum2-sum1即为所缺失的数字。

方法2：二分
前面两种方法的时间复杂度都是，但是题目给我们的要求是能不能用来解决这道题目呢？
其实我们看到这个时间复杂度，最容易想到的就是二分查找。其实主要还是利用下标与值相等这个条件，去维护左右边界，然后最终找到缺失的那个数字。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型一维数组 给定的数字串
     * @return int整型
     */
    public int solve (int[] a) {

//         return method1(a);

        return method2(a);
    }

    public int method1 (int[] a) {
        int aLen = a.length;
        int presum = aLen * (aLen + 1) / 2;
        int sum = 0;
        for (int i=0;i<aLen;i++)
            sum += a[i];
        return presum - sum;
    }

    public int method2 (int[] a) {

        int left = 0;
        int right = a.length - 1;

        while (left <= right) {

            int mid = left + (right - left) / 2;

            if (a[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }


            }
        return left;
        }
    }