[interview question 17.04. missing numbers]

---

One 、 Subject requirements

Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer . You have a way O(n) Is it finished in time ？
Example 1：
Input ：[3,0,1]
Output ：2
Example 2：
Input ：[9,6,4,2,3,5,7,0,1]
Output ：8

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/missing-number-lcci/

Two 、 Thought analysis

Train of thought ：
n Add the numbers and subtract nums Add all numbers

int missingNumber(int* nums, int numsSize){
    
    int sum = (0 + numsSize) * (numsSize + 1) / 2;
    int sumnum = 0;
    for(int i = 0;i < numsSize; i++)
    {
    
        sumnum += nums[i];
    }
    return sum - sumnum;

}

Train of thought two ：
n Number XOR , And again nums Exclusive or

Tips ：0 And any number XOR gets itself ( Self means anything that is related to 0 The number of exclusive or )

int missingNumber(int* nums, int numsSize){
    
    int sum = 0;
   for(int i = 0 ;i <= numsSize ;i++)
   {
    
       sum ^= i;
   }
   for(int i = 0 ;i < numsSize ;i++)
   {
    
       sum ^= nums[i];
   }
   return sum;
}

---

The above is the whole content of this article , If there are mistakes in the article or something you don't understand , Communicate more with meow bloggers . Learn from each other and make progress . If this article helps you , Can give meow bloggers a concern , Your support is my biggest motivation .