在线性时间内找出排序向量中是否有一对相加等于某个值

Question

给定一个std::vector按升序排序的不同元素，我想开发一种算法来确定集合中是否有两个元素的总和为某个值，sum。

我已经尝试了两种不同的方法，并进行了各自的权衡：

1. 我可以扫描整个向量，对于向量中的每个元素，对向量应用二分搜索 ( std::lower_bound) 以搜索sum与当前元素之间的差异对应的元素。这是一个不需要额外空间的 O(n log n) 时间解决方案。

2. 我可以遍历整个向量并填充std::unordered_set. 然后，我扫描向量，对于每个元素，我在 中查找与当前元素std::unordered_set之间的差异sum。由于对哈希表的搜索平均以恒定时间运行，因此该解决方案以线性时间运行。但是，由于std::unordered_set数据结构的原因，此解决方案需要额外的线性空间。

尽管如此，我正在寻找一种在线性时间内运行且不需要额外线性空间的解决方案。有任何想法吗？似乎我被迫用速度换取空间。

Answer 1

由于std::vector已经排序并且您可以即时计算一对的总和，您可以在 O(1) 空间的向量大小中实现线性时间解。

下面是一个类似 STL 的实现，它不需要额外的空间并在线性时间内运行：

template<typename BidirIt, typename T>
bool has_pair_sum(BidirIt first, BidirIt last, T sum) {
    if (first == last)
        return false; // empty range

   for (--last; first != last;) {
      if ((*first + *last) == sum)
         return true; // pair found

      if ((*first + *last) > sum)
         --last; // decrease pair sum
      else // (*first + *last) < sum (trichotomy)
         ++first; // increase pair sum
   }

    return false;
}

这个想法是从两端（前后）同时以相反的方向遍历向量，并在这样做的同时计算这对元素的总和。

一开始，该对分别由具有最低值和最高值的元素组成。如果结果总和小于sum，则前进first- 指向左端的迭代器。否则，last向后移动——指向右端的迭代器。这样，产生的总和逐渐接近sum。如果两个迭代器最终都指向同一个元素并且没有sum找到总和等于 的对，则不存在这样的对。

auto main() -> int {
   std::vector<int> vec{1, 3, 4, 7, 11, 13, 17};

   std::cout << has_pair_sum(vec.begin(), vec.end(), 2) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 7) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 19) << ' ';
   std::cout << has_pair_sum(vec.begin(), vec.end(), 30) << '\n';
}

输出是：

0 1 0 1

由于函数模板的通用性，has_pair_sum()并且因为它只需要双向迭代器，所以这个解决方案也适用std::list：

std::list<int> lst{1, 3, 4, 7, 11, 13, 17};
has_pair_sum(lst.begin(), lst.end(), 2);

Answer 2

我和 ????? 的答案中的想法相同。，但有一点更容易理解的实现。

bool has_pair_sum(std::vector<int> v, int sum){
    if(v.empty())
        return false;

    std::vector<int>::iterator p1 = v.begin();
    std::vector<int>::iterator p2 = v.end(); // points to the End(Null-terminator), after the last element
    p2--; // Now it points to the last element.

    while(p1 != p2){  
        if(*p1 + *p2 == sum)
            return true;
        else if(*p1 + *p2 < sum){ 
            p1++;
        }else{
            p2--;
        }
    }

    return false;
}