268.md

268. Missing Number

Leetcode link

解题思路——加总

本题要我们求一个值由 0 ~ n 组成的长度为 n 的数组里缺失的数字

总共有两种方法来求解，第一种思路是：

用 0 ~ n 的加总减去数组元素的加总

C++

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();
        for(int i=0;i<nums.size();i++) {
            res += i - nums[i];
        }
        return res;
    }
};

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let len = nums.length;
    let sum = nums.reduce((prev, cur)=>prev + cur, 0);
    return len * (len + 1) / 2 - sum;
};

解题思路——亦或

另一种思路则是用到了亦或的操作：

• 我们把所有数组元素进行亦或
• 然后把 0 ~ n 的数字也进行亦或
• 最后把上述两个结果亦或就是答案了

C++

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();
        int i = 0;
        for(int num : nums) {
            res ^= num ^ i++;
        }
        return res;
    }
};

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let res = nums.length, cur = 0;
    for(let num of nums) {
        res ^= num ^ cur;
        cur++;
    }
    return res;
};