letcode刷题n12-q268：丢失的数字

这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战

题目描述

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

 

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
 

提示：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路 & CODE

题目说给定的范围是[0,n]，也就是说这个范围中有n+1个数，但是给定的数组中只有n个数，且数组中的数字不重复，那么丢失的数字就在[0,n]的区间范围内

1. 求和

我们只需要对题目给的数组中所有元素求和，再将[0,n]间的所有元素求和，进行减法运算，最后得出的结果就是丢失的数字

public int missingNumber1(int[] nums) {
    int sumData = 0;
    for (int num : nums) {
        sumData += num;
    }
    return sum(nums.length) - sumData;
}

public int sum(int num) {
    if (num == 0) {
        return num;
    }
    return num + sum(num - 1);
}
复制代码

翻了一下题解，还是人家数学基础好啊，[0,n]不就是个等差数列嘛，等差数列求和公式为n(n+1)/2，何必傻傻用递归...

public int missingNumber(int[] nums) {
    int n = nums.length;
    int total = n * (n + 1) / 2;
    int arrSum = 0;
    for (int i = 0; i < n; i++) {
        arrSum += nums[i];
    }
    return total - arrSum;
}
复制代码

2. 位运算

位运算，看了评论区瞬间想起了前几天做的题目【n6-q136：只出现一次的数字】，只有一个数字落单，其它数字全部成对出现，全部为运算后结果就为只出现一次的数字。

这里我们有两个数组，题目给的数组和[0,n]中所有数字组成的数组，把两个元素合并到一起，只有那个丢失的数组出现了一次！

public int missingNumber2(int[] nums) {
    int res = 0;
    for (int i = 0; i <= nums.length; i++) {
        if (i == nums.length) {
            res = res ^ i;
        } else {
            res = res ^ i ^ nums[i];
        }
    }
    return res;
}
复制代码

虽然是几天前的做的，但是第一时间还是没能想出这种解法，多做多总结，这些常用解法形成肌肉记忆就行了吧！

3. 哈希

数组的每道题都可以哈希...