在 C++ 中的集合中实现两个指针技术

Question

我正在尝试在 C++ 的集合中实现两个指针技术。我想检查集合中两个元素的差值是否等于常数 'k'.

void solve(int n,int k,set<int> s){
    auto it_1 = s.begin();
    auto it_2 = s.end();
    while(it_1 < it_2){ 
        if(*it_2 - *it_1 == k){
            cout << "YES" << endl;
            return;
        }
        else if(*it_2 - *it_1 > k){
            it_1++;
        }
        else{
            it_2--;
        }
    }
    cout << "NO" << endl;
    return;
}

我收到以下错误：-

error: no match for 'operator<' (operand types are 'std::_Rb_tree_const_iterator' and 'std::_Rb_tree_const_iterator') while(it_1 < it_2)

我知道错误是因为我在比较两个指针。如何检查 it_1 是否在 it_2 后面？

Answer 1

迭代器的问题可以很快解决。

只需使用 != 运算符而不是 <
不从end迭代器开始，而是从前一个元素开始。因为 end-迭代器指向过去的最后一个有效元素。

但是，不幸的是，如果您想找到具有给定增量的一对，2 指针方法将不起作用。这样做的原因是您会过多地增加一个指针，并且永远无法达到增量。通过总结这些值，它会起作用。

让我们以您的初始方法为例修复小错误并查看输出：

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::prev(s.end());
    while (it_1 != it_2) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if (*it_2 - *it_1 == k) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 - *it_1 > k) {
            it_1++;
        }
        else {
            it_2--;
        }
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

这将导致：

你看到问题了。

顺便说一句，求和是 2 指针方法的典型用例。然后它将始终有效。该集合已排序。我们从开头的最小值和结尾的最大值开始。因此，构建第一个总和将为我们提供最大可能的总和。然后我们先移动小数字的指针，或者根据总和，减少上面的指针。

示例：

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::prev(s.end());
    while (it_1 != it_2) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if (*it_2 + *it_1 == k) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 + *it_1 < k) {
            it_1++;
        }
        else {
            it_2--;
        }
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

输出：

但是delta问题怎么解决呢？

永远有效的方法是暴力破解。这会像这样：

#include <iostream>
#include <set>

void solve(int k, std::set<int>& s) {
    auto it_1 = s.begin();
    auto it_2 = std::next(s.begin());

    while ((it_1 != s.end()) and (it_2 != s.end())) {
        std::cout << *it_1 << ' ' << *it_2 << '\n';
        if ((it_1 != it_2) and ((*it_2 - *it_1 == k) or (*it_1 - *it_2 == k))) {
            std::cout << "YES\n";
            return;
        }
        else if (*it_2 - *it_1 < k)
            ++it_2;
        else
            ++it_1;
    }
    std::cout << "NO\n";
    return;
}
int main() {
    std::set test{ 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };
    solve(8, test);
}

输出如下：

稍微优化一下的反对意见会使用 std::unordered_map。但也许这对这里来说太多了。

在 C++ 中的集合中实现两个指针技术

Implementing two pointer technique in sets in C++

c++

set