21xrx.com
2024-11-05 19:02:10 Tuesday
登录
文章检索 我的文章 写文章
C++实现两数之和
2023-07-03 13:26:30 深夜i     --     --
C++ 实现 两数之和

C++是一门非常适合算法和数据结构的高级编程语言,在这里,我们将讨论如何使用C++实现两数之和。C++鲜有原生的实现方案,通常需要我们自己编写代码来实现这个功能。

首先,让我们来看看这个问题的简单版本:给定两个整数,求它们的和。我们可以使用以下代码实现:


#include<iostream>

using namespace std;

int main()

{

  int a = 10, b = 20;

  int sum = a + b;

  cout<<"The sum of "<<a<<" and "<<b<<" is "<<sum<<endl;

  return 0;

}

在这段代码中,我们先定义了两个整数a和b,并将它们相加。然后,我们将结果存储在sum变量中,并打印出结果。输出结果为:The sum of 10 and 20 is 30。

但这只是一个简单的示例,现在我们来考虑更一般的情况:如果我们有一个整数数组,如何找到两个元素的和等于一个给定值?

我们需要遍历该数组,并寻找一个满足条件的二元组。一种简单的实现方式是使用嵌套循环,代码如下:


#include<iostream>

using namespace std;

int main()

{

  int a[] = 5;

  int n = sizeof(a) / sizeof(a[0]);

  int target = 7;

  

  for(int i = 0; i < n; i++)

  {

    for(int j = i + 1; j < n; j++)

    {

      if(a[i] + a[j] == target)

      {

        cout<<"The pair is: "<<a[i]<<", "<<a[j]<<endl;

      }

    }

  }

  

  return 0;

}

在上面的代码中,我们首先定义了一个整数数组a和目标值target。我们然后计算该数组的大小,并使用嵌套循环扫描所有可能的二元组。如果找到了一个满足条件的二元组,则输出该组。

这个算法的时间复杂度为O(n²),这意味着如果数组很大,它的执行时间会很长。因此,我们需要更好的算法来解决这个问题。

一个更好的解决方案是使用哈希表。我们可以将每个元素插入哈希表中并检查和欲求的元素是否已经存在。代码如下:


#include<iostream>

#include<unordered_map>

using namespace std;

int main()

{

  int a[] = 3;

  int n = sizeof(a) / sizeof(a[0]);

  int target = 7;

  

  unordered_map<int, int> mp;

  for(int i = 0; i < n; i++)

  {

    int num = target - a[i];

    if(mp.find(num) != mp.end())

    {

      cout<<"The pair is: "<<a[i]<<", "<<num<<endl;

    }

    mp[a[i]] = i;

  }

  

  return 0;

}

在上面的代码中,我们首先定义了一个哈希表mp以及目标值target。在循环数组时,我们计算当前元素和目标元素之间的差值,并检查这个差值是否已经存在于哈希表中。是,则输出对应的元素值;否则,将当前元素插入哈希表中,以便之后的查找。

这个算法的时间复杂度为O(n),它比嵌套循环的时间复杂度O(n²)更优秀,尤其是在数组非常大的情况下。

综上所述,我们已经学会了使用C++实现两数之和的方法。我们可以使用嵌套循环和哈希表两种算法,前者时间复杂度较高,适用于数组较小的情况下;后者时间复杂度更低,适用于数组非常大的情况。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复