Дан вектор и цели сумму, возвращает ноль-на основе индексов любых двух различных элементов, сумма которых равна целевой суммы


Я пытаюсь решить 4. Две суммы из этого набора c++ интервью вопросы. Насколько я думаю, это решение имеет сложность \$О(Н \зарегистрируйте N)\$ может быть дополнительно оптимизирована?

Написать функцию, которая, учитывая вектор и цели сумму, возвращает индексы с нуля любых двух различных элементов, сумма которых равна целевую сумму. Если таких элементов нет, функция должна вернуться (-1, -1).

Например, findTwoSum({ 1, 3, 5, 7, 9 }, 12) должны вернуть std::pair<int, int> содержащие любое из следующих пар показателей:

  • 1 и 4 (3 + 9 = 12)
  • 2 и 3 (5 + 7 = 12)
  • 3 и 2 (7 + 5 = 12)
  • 4 и 1 (9 + 3 = 12)

Вот мой подход, учитывая, что отрицательных чисел не может присутствовать в векторе

static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
    std::vector<int> com;
    std::vector<int>::iterator it;
    for(unsigned count=0; count<list.size(); count++){
        it = std::find(com.begin(), com.end(), list[count]);
        if ( it != com.end() ){
            return std::make_pair(it - com.begin() + 1, --count);
        }
        else{
            if(sum >= list[count])
            com.push_back(sum-list[count]);
        }

    }
    return std::make_pair(-1,-1);
}


Комментарии