268. 丢失的数字

 

傻傻的想了半天，看了题解才想起来高斯求和，真的巧妙。

高斯求和，高中数列得知识，等差数列之和=（首项+尾项）*项数/2

根据题意可得只少一个元素，那么先算出和然后再迭代一次减去所有元素即可

时间O(n)，空间O(1)

public int missingNumber(int[] nums) {
        int sum = (1+nums.length)*nums.length/2;
        for (int num:nums){
            sum-=num;
        }
        return sum;
    }

进阶：

本题中由于n的范围是10^4，所以我们使用高斯求和时不用担心溢出的问题，但是当

范围扩大到10^5时，就无法继续这么使用了，为了应对这个问题，我们做了一点优化，

不一次性的去计算和，而是在遍历中一边求和一遍求差。

相比高斯求和的方法，优点在于避免了溢出的风险，缺点在于拆分计算数组和增加了计算次数

    public int missingNumber(int[] nums) {
        // 数组下标无法达到n，因此这里初始化时就要赋值
        int sum=nums.length;
        for(int i=0;i<nums.length;i++){
            // 拆分实现高斯求和法中的等差数列求和操作
            sum+=i;
            sum-=nums[i];
        }
        return sum;
    }