After reading this article , You can go and get the following questions ：

448. Find all the missing numbers in the array

**-----------**

I've also written a few interesting intelligence questions before , Let's talk about another clever topic today .

The topic is very simple ：

Give a length of n Array of , Its index should be in `[0,n)`

, But now you have to put it in n + 1 Elements `[0,n]`

, So there must be one element that can't hold it , Please find out the missing element .

The problem is not difficult , It should be easy for us to think of , Put this array in order , And then go through it , Isn't it easy to find the missing element ？

Or say , By virtue of the characteristics of data structures , Use one HashSet Save all the numbers in the array , Re traversal `[0,n]`

Number between , Go to HashSet Query in , It's also easy to find out the missing element .

The time complexity of sorting solution is O(NlogN),HashSet The time complexity of the solution is O(N), But it needs to be O(N) Space complexity storage of HashSet.

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

** The third method is bit operation **.

For exclusive or operations （`^`

）, We know it has a special property ： A number is XOR with itself, and the result is 0, A number and 0 Do XOR or itself .

And XOR operations satisfy the laws of exchange and union , in other words ：

2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

The missing element can be figured out by these properties . for instance `nums = [0,3,1,4]`

：

For ease of understanding , Let's assume that we fill in the index first , Then make each element correspond to its own equivalent index ：

After doing so , You can find that in addition to the missing elements , All the indexes and elements form a pair , Now, if you put this single index 2 To find out , And you find the missing element .

How to find this single figure ,** Just XOR all the elements and indexes , The numbers in pairs will disappear into 0, Only this single element is left **, We have achieved our goal .

```
int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// First XOR with the new index
res ^= n;
// And other elements 、 Index XOR
for (int i = 0; i < n; i++)
res ^= i ^ nums[i];
return res;
}
```

Because the XOR operation satisfies the commutative law and the associative law , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

thus , Time complexity O(N), Spatial complexity O(1), We've reached the best , Should we just go back home ？

If you think so , It shows that we are too poisoned by the algorithm , As we learn more and more knowledge , On the contrary, it is easy to fall into the fixed pattern of thinking , There is actually a very simple solution to this problem ：** The summation formula of the sequence of equal differences **.

The meaning of the title can be understood in this way ： Now there's an arithmetic sequence 0, 1, 2,..., n, One of the missing numbers , Please find it out . So this number is not `sum(0,1,..n) - sum(nums)`

Well ？

```
int missingNumber(int[] nums) {
int n = nums.length;
// The formula ：( First item + Last item ) * Number of items / 2
int expect = (0 + n) * (n + 1) / 2;
int sum = 0;
for (int x : nums)
sum += x;
return expect - sum;
```

You see , This solution should be the simplest , But tell the truth. , I didn't think of this solution myself , And I went to ask some big guys , They didn't think of the simplest idea either . contrary , If you ask a junior high school student , He may soon be able to think of .

It's done , Should we just go back home ？

If you think so , It shows that our control of the details is almost perfect . In calculating with the summation formula `expect`

when , You think about it ** The integer overflow ** Do you ？ If the result of multiplication is too large to cause overflow , Then the result must be wrong .

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

Our idea just now is to add both sums and subtract them , To avoid spillage , Just sum and subtract at the same time . It's very similar to the idea of bit operation , Still assuming `nums = [0,3,1,4]`

, First fill in an index and then match the element with the index ：

We let each index subtract its corresponding element , And add up the results of subtraction , It's the missing element ？

```
public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
// New index
res += n - 0;
// Add up the difference between the index and the element
for (int i = 0; i < n; i++)
res += i - nums[i];
return res;
}
```

Because addition and subtraction satisfy the law of exchange and law of combination , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

So far, this algorithm has gone through nine twists and eighteen turns , Finally, there is no more pit .

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！