公式的含义如何在数组中找到丢失的元素？

Question

任务是在数组中找到丢失的元素。我理解解决方案的逻辑，但我不明白这个公式是如何工作的？

这是解决方案

int[] array = new int[]{4,1,2,3,5,8,6};
   int size = array.length;
   int result = (size + 1) * (size + 2)/2;
   for (int i : array){
       result -= i;
   }

但是为什么我们将总大小加 1 并将其乘以总大小 + 2 /2 ?? 在所有资源中，人们只使用该公式，但没有人解释该公式的工作原理

Answer 1

1thru的数字总和n等于((n)(n+1))/2。

例如对于 1,2,3,4,5 5*6/2 = 15。

但是，这仅仅是一个快速的方法来从加起来的数字1来n。这是真正发生的事情。

该系列计算的总和1来n假设他们都出席了会议。但是通过从该总和中减去每个数字，余数就是缺失的数字。

从k到n相邻元素相差 1的整数的等差数列的公式是。

S _[k,n] = (n-k+1)(n+k)/2

示例：k = 5，n = 10

• S _[k,n] = 5 6 7 8 9 10

• S _[k,n] = 10 9 8 7 6 5

• S _[k,n] = (10-5+1)*(10+5)/2

• 2S _[k,n] = 6 * 15 / 2

• S _[k,n] = 90 / 2 = 45

对于序列中缺失的任何单个数字，通过从 45 的总和中减去其他数字，余数将是缺失的数字。

Answer 2

假设您的数组中目前有 n 个元素。您知道 缺少一个元素，这意味着数组的实际大小应该是 n + 1。

现在，您只需要计算总和 1 + 2 + ... + n + (n+1)。

计算从 1 到 k 的所有整数之和的方便公式由 k(k+1)/2 给出。

只需将 k 替换为 n+1，即可得到公式 (n+1)(n+2)/2。