在线性时间中查找排序后的向量中是否有一对加起来等于某个值

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

我的想法与the answer of 眠りネロク中的想法相同，但实现起来更容易理解。

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;
}

Answer 3

好吧，由于已经给了排序数组，我们可以使用两种指针方法，将左指针保持在数组的开头，将右指针保持在数组的末尾，然后在每次迭代中检查是否left的值之和指针索引和右指针索引的值是否相等，如果是，则从此处返回，否则我们必须决定如何减小边界，即增大左指针或减小右指针，因此我们将给定的临时总和进行比较总和，如果此临时总和大于给定总和，则我们决定减少右指针，如果我们增加左指标，则临时总和将保持不变或仅增加，但绝不会减小，因此我们决定减少右指针，以便临时总和减少，并且我们接近给定总和，如果临时总和小于给定总和，则相似，因此减少临时指针的意义不大，因为临时总和将保持总和或减少更多，但永远不会增加，因此我们增加了左指针，所以速度rary sum增加，我们达到给定的总和，并且一次又一次地执行相同的过程，除非我们得到相等的和，或者左指针索引值变得大于右指针索引值，反之亦然下面是演示代码，如果不清楚，请告诉我

bool pairSumExists(vector<int> a, int sum){
    if(a.empty())
    return false;

    int len = a.size();
    int left_pointer = 0  , right_pointer = len - 1;

    while(left_pointer < right_pointer){
        if(a[left_pointer] + a[right_pointer] == sum){
            return true;
        }
        if(a[left_pointer] + a[right_pointer] > sum){
            --right_pointer;
        }
        else
        if(a[left_pointer] + a[right_poitner] < sum){
            ++left_pointer;
        }
    }
    return false;
}