请解释这个在1.N中找到缺失数的过程。

Question

我们得到了一个n-1整数的列表，这些整数在1到n的范围内，列表中没有重复。列表中缺少一个整数。我们得找到失踪的号码。这就是问题所在。

我的方法是获取来自1.N的所有元素的XOR和数组中的所有元素，然后输出XOR。它工作的很好，但我找到了另一个解决方案，在极客为极客，但我无法理解什么和为什么要这样做。

方法：我们可以从已知数字中选择一个数字，并从给定的数字中减去一个数字。

码

#include <bits/stdc++.h> 
using namespace std; 

// a represents the array 
// n : Number of elements in array a 
int getMissingNo(int a[], int n)  
{  
    int i, total=1;  

for ( i = 2; i<= (n+1); i++) 
{ 
    total+=i; 
    total -= a[i-2]; 
} 
return total;  
}  

//Driver Program 
int main() { 
    int arr[] = {1, 2, 3, 5}; 
    cout<<getMissingNo(arr,sizeof(arr)/sizeof(arr[0])); 
    return 0; 
}

Answer 1

int i, total=1; 

由于我们已将总计声明为整数，如果加法超出整数上限，则在添加所有数字时可能会出现溢出。

因此，为了克服这个问题，我们同时从总数中添加(从1到N)和减去(数组a[]的元素)。

for ( i = 2; i<= (n+1); i++) 
{ 
    total+=i; 
    total -= a[i-2]; // This will reduce the total so that overflow does not happen.
} 

Answer 2

使用求和公式：

I=1至N=N* (N + 1) /2的和

https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

添加列表中的数字。从数字之和中减去这个值，你就会得到你丢失的数字。