-3

我一直在寻找有关矢量迭代的一些技巧。我正在尝试完成一个挑战，您必须实现一个函数 (SumOfTwo)，该函数接受两个向量和一个总和作为参数，并且必须检查两个向量中是否有任何一对数字，如果相加可以给出总和这是作为参数传递的。

我的功能工作正常，只是它不包括 500 毫秒的时间限制。我觉得有更好的方法来遍历两个向量而不是两个 for 循环，但我觉得很卡住......

bool sumOfTwo(std::vector<int> a, std::vector<int> b, int v) {
    if((a.empty()) || b.empty()){
        return false;
    }
    for (std::vector<int>::iterator it1 = a.begin(); it1<=a.end(); ++it1)     {
            for (std::vector<int>::iterator it2 = b.begin(); it2<=b.end(); ++it2) {
                if ((*it1 + *it2) == v){
                    return true;
                }
            }
    }
    return false;
}
4

3 回答 3

5

关于样式提示，将您的代码更改为以下（为了效率和整洁）

bool sumOfTwo(const std::vector<int>& a, const std::vector<int>& b, int v) {
    for (auto i1 : a)     {
            for (auto i2 : b) {
                if ((i1 + i2) == v){
                    return true;
                }
            }
    }
    return false;
}

考虑使用std::unordered_set和交叉引用来确定总和是否可能实现最大效率。请记住，在 an 中的查找std::unordered_set是 O(1)

于 2017-05-15T20:21:09.330 回答
3

为什么算法慢？

目前您正在迭代两个向量，但您正在进行嵌套迭代。让我们将向量的长度称为m和n（任意）。您当前的算法是 O(n*m)，这对于大向量来说非常慢。

如果 m = n = 1000，在最坏的情况下（没有两个元素总和为v），您正在执行数百万次操作——哇！

我怎样才能提高性能？

我可以想到一个巨大的加速：给定一个向量、、a一个向量b和一个期望的总和v，你可以从 and 的元素差异创建一组数字，v并a检查其中的任何值b是否在集合中。

伪代码是：

if a.empty or b.empty:
    return false

set = emptySet

for e in a:
    set.add(v - e)

for e in b:
    if e in set:
        return true

return false

无序集中的查找应该是 O(1)，所以这是一个 O(max(m, n)) 算法，其中 m 是长度，an 是长度b。

如果 m = n = 1000，在最坏的情况下，您现在正在执行数千次操作——要好得多，对吗？

在 C++ 中实现这一点留给读者。:)

提示：通过引用传递对向量来说是个好主意。

于 2017-05-15T20:25:06.810 回答
2

感谢大家的大力帮助！我解决时间限制的方法是：

bool sumOfTwo(std::vector<int>& a, std::vector<int>& b, int v) {
   if((a.empty()) || b.empty()){
       return false;
   }
   std::unordered_set<int> s;
   for (const auto i : a) {
       s.insert(v-i);
   }
   for (const auto i : b) {
      auto search = s.find(i);
      if (search != s.end()) {
          return true;
      }
   }
   return false;
}
于 2017-05-15T21:08:56.200 回答