时间戳

首页 > 解决方案 > C++如何优化这个算法？（标准：：地图）

c++ - C++如何优化这个算法？（标准：：地图）

问题描述

问题如下：给定一个数字's'，s ∈ [0, 10^6]，和一个数字'n'，n ∈ [0, 50000]，然后是n个数字，我们必须找出如何许多数字对的总和等于“s”数（我们必须使用映射或集合来解决它）

这是示例：

输入：

5 (this is s)
6 (this is n)
1 
4 
3 
6 
-1 
5

输出：

2

解释：这些是 (1,4) 和 (6,−1) 对。(1 +4 = 5 和 6 + (-1) = 5)

这是我的“解决方案”，我什至不知道它是否正确，但它适用于我们得到的示例。

#include <iostream>
#include <map>
#include <iterator>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s;
    cin >> s;
    int n;
    cin >> n;
    map<int, int> numbers;

    int element;
    int counter = 0;
    for(int i=0; i<n;i++)
    {
        cin >> element;
        numbers.insert(pair<int, int>(element, s-element));

    }
    for(map<int, int>::iterator it = numbers.begin(); it != numbers.end(); it++)
    {
        map<int, int>::iterator it2 = it;
        while(it2 != numbers.end())
        {
            if(it->second == it2->first)
            {
                counter++;
                break;
            }
            it2++;

        }
    }
    cout << counter << "\n";
    return 0;
}

感谢您提前回答！我仍然是初学者，我正在学习，对不起。

标签： c++c++14

解决方案

element, s-element是个好主意，但没有理由存储所有对，然后才检查重复项。这将删除O(n^2)您最后的循环。

使用散列的标准方法是：

seen=unordered_map<number,count>() 
for 1...n:
  e = read_int()
  if (s-e) in seen:
    duplicates+=seen[s-e] # Found new seen[s-e] duplicates.
  if e in seen:
    seen[e]+=1
  else:
    seen.insert(e,1)

return duplicates

推荐阅读