C++程序查找前N个自然数的和

给定一个数字N，查找前N个自然数的总和。

C++程序查找前N个自然数的和

例子：

输入： n = 3
输出： 6
解释： 注意1 + 2 + 3 = 6

输入： 5
输出： 15
解释： 注意是1 + 2 + 3 + 4 + 5 = 15

一个 简单的做法 可以如下所示。

1）初始化：sum = 0
2）从x = 1到n循环执行以下内容。
sum = sum + x

// C++程序查找前
// n个自然数的总和
#include<iostream>
using namespace std;
  
// 返回前n个自然数的总和
int findSum(int n)
{
   int sum = 0;
   for (int x = 1; x <= n; x++) 
     sum = sum + x;
   return sum;
}
  
// 主函数
int main()
{
  int n = 5;
  cout << findSum(n);
  return 0;
}

输出：

时间复杂度： O(n)

辅助空间： O(1)

一个 高效的解法 是使用下面的公式。

C++程序查找前N个自然数的和

这是如何工作的？

我们可以使用归纳法来证明这个公式。
n = 1和n = 2时是正确的。
当n = 1时，总和 = 1 * (1 + 1)/2 = 1
当n = 2时，总和 = 2 * (2 + 1)/2 = 3

假设k = n-1时是正确的。

k个数字的总和 = (k * (k+1))/2
将k = n-1代入以后，我们得到
k个数字的总和 = ((n-1) * (n-1+1))/2
                 = (n - 1) * n / 2

如果我们加上n，则得到，
n个数字的总和 = n + (n - 1) * n / 2
                 = (2n + n2 - n)/2
                 = n * (n + 1)/2

// 高效的C++程序查找前
// n个自然数的总和
#include<iostream>
using namespace std;
  
// 返回前n个自然数的总和
int findSum(int n)
{
   return n * (n + 1) / 2;
}
  
// 主函数
int main()
{
  int n = 5;
  cout << findSum(n);
  return 0;
}

输出：

时间复杂度： O(1)

辅助空间： O(1)

// 高效的C++程序查找前
// n个自然数的总和
// 如果结果不超过限制，可以避免溢出。
#include<iostream>
using namespace std;
   
// 返回前n个自然数的总和
int findSum(int n)
{
   if (n % 2 == 0)
  
      // 在这里，乘以1LL有助于在long long中进行计算，
      // 以便答案不会溢出。
      return (n / 2) * 1LL * (n + 1); 
   
   // 如果n是奇数，则(n+1)必须是偶数。
   else
  
      // 在这里，乘以1LL有助于在long long中进行计算，
      // 以便答案不会溢出。
      return  ((n + 1) / 2) * 1LL * n; 
}
   
// 主函数
int main()
{
  int n = 5;
  cout << findSum(n);
  return 0;
}

输出：

时间复杂度： O(1)

辅助空间： O(1)