c++ - 如何返回 vector 的2个索引？

Question

我正在编写此程序以在 vector 中查找2个数字( vector 未排序)，以使其总和等于目标总和。这是我的程序:

#include <vector>
#include <algorithm>
using namespace std;

vector<size_t> find_numbers(const vector<int>& nums, int target) 
{
    sort(nums.begin(), nums.end()); // Sort the vector

    for (size_t i = 0; i < nums.size(); ++i)
        if (binary_search(nums.begin(), nums.end(), target - nums[i]))
            return {i, ?}; // How to return the second number's position?

    return {};
}

如果我添加另一个循环来查找第二个数字的位置，则运行时间将为O(n ^ 2)，我希望程序在O(nlogn)中运行。如何返回第二个数字的位置？

Answer 1

std::binary_search 只是返回一个bool，指示您要查找的元素是否存在。没有返回有关此元素位置的信息。
而是使用合适的算法 std::lower_bound 进行二进制搜索，并返回您要查找的元素(如果存在)应位于的位置。因此，您可以像这样实现它:

for (size_t i = 0; i < nums.size(); ++i)
{
   auto it = std::lower_bound(nums.begin(), nums.end(), target - nums[i]);
   if (it != nums.end() && *it == target - nums[i])
     return {i, std::distance(nums.begin(), it};
}

同样，函数的返回类型是 vector<int>，它将起作用，但是由于您总是返回正好2个值，因此我建议改用 std::pair<int, int>。