Leetcode две суммы
В настоящее время я изучаю C ++ на базе Python, поэтому я включу решение на Python и C ++ для следующей постановки проблемы:
Учитывая массив целых чисел nums и целочисленную цель, верните индексы двух чисел так, чтобы они складывались в цель. Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды. Вы можете вернуть ответ в любом порядке.
Пример 1:
Ввод: числа = [2,7,11,15], цель = 9
Выход: [0,1]
Пример 2:
Ввод: число = [3,2,4], цель = 6
Выход: [1,2]
Я хотел бы услышать ваши отзывы / предложения по улучшению производительности / другие предложения. Вот ссылка
two_sum.py
def two_sum(nums: list, target: int):
for i, n in enumerate(nums):
match = target - n
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
if __name__ == '__main__':
if result := two_sum([2, 7, 11, 15], 22):
print(f'Indices:\n{result}')
else:
print('No matches found')
Статистика Leetcode:
Время выполнения: 772 мс, быстрее, чем 36,98% онлайн-представлений Python для Two Sum. Использование памяти: 14,4 МБ, менее 49,82% онлайн-представлений Python для Two Sum.
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
vector<int> two_sum_solution(vector<int> &nums, int target) {
vector <int> results;
for (int i = 0; i < nums.size(); ++i) {
int match = target - nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] == match) {
for (int index_match : {
i, j
})
results.push_back(index_match);
}
}
}
return results;
}
#endif //LEETCODE_TWO_SUM_H
main.cpp
#include <vector>
#include "two_sum.h"
using std::vector;
int main() {
vector<int> v1{2, 7, 11, 15};
vector<int> v = two_sum_solution(v1, 22);
if (!v.empty()) {
cout << "Indices:" << endl;
for (auto i: v)
cout << i << " ";
}
else (cout << "No matches found");
}
Статистика Leetcode:
Время выполнения: 384 мс, быстрее, чем 34,03% онлайн-представлений C ++ для Two Sum. Использование памяти: 9,3 МБ, менее 12,99% онлайн-представлений C ++ для Two Sum.
Ответы
Я не специалист по C ++, но могу высказать свое мнение о решении Python.
Ваше текущее решение работает в \$O(n^2)\$. В основном, для каждого номера nвхода numsнайдите target - nв nums. Как это улучшить?
Вторую часть алгоритма можно улучшить из \$O(n)\$к \$O(1)\$. Вместо того, чтобы искать target - nв списке, вы можете использовать словарь:
def two_sum(nums: list, target: int):
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
Полученные результаты:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Включите только те файлы заголовков, которые вам нужны
В вашем two_sum.hфайле он вам не нужен iostream, поскольку вы не используете его функциональные возможности. Помните, что #includeфайл буквально копируется и вставляется, поэтому, если вы включаете этот файл заголовка в несколько файлов, это может потенциально замедлить время компиляции.
Разделить объявления и определения
Обычно файлы разбиваются на две части: файл заголовка (обычно заканчивающийся на *.h, *.hpp, *.hh) и исходный файл (обычно заканчивающийся на *.cpp, *.cc). Заголовочный файл состоит только из объявлений, а исходный файл содержит реализацию.
Итак, в вашем случае ваш заголовочный файл будет выглядеть так:
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <vector>
std::vector<int> two_sum_solution(std::vector<int> &nums, int target);
#endif // LEETCODE_TWO_SUM_H
и ваш исходный файл будет выглядеть так:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Фактически, если вы попытаетесь включить свой two_sum.h(с реализацией) в несколько файлов, вы нарушите правило одного определения . Ваши исходные файлы будут содержать несколько определений одной и той же функции, и компоновщик выдаст ошибку. Один из способов обойти - отметить функции inline, но вы, скорее всего, захотите сделать первое.
Нет using namespaceв заголовочных файлах
Не делайте using namespaceни одного его варианта в заголовочном файле. Поскольку файл заголовка копируется и вставляется во множество исходных файлов, он может вызвать досадные ошибки. Глянь сюда
Использовать константную ссылку
Поскольку вектор two_sum_solutionне изменяется nums, передайте его по ссылке const.
size_t vs int для индексов массива
Рассмотрите возможность использования size_t вместо int для индексов массива
Используйте autoкак можно больше
В вашем коде есть несколько экземпляров, которые вы можете использовать autoвместо указания типа. Примеры:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
Самый внутренний цикл бессмыслен
Просто делай
results.push_back(i);
results.push_back(j);
Кроме того, как только вы найдете решение, вы можете сразу же вернуть результат.
Возможно, вы можете улучшить производительность, создав карту значения -> индекс в первой итерации по данному массиву.
В настоящее время Ваша программа выполняет следующие функции (временная сложность):
- перебирать все
index, valueпары массива ( \$ O(n) \$) - искать
target - valueв массиве ( \$ O(n) \$) - индекс поиска
target - value( \$ O(n) \$)
И поскольку все они вложены, вы получаете \$ O(n^2) \$(это не \$ n^3 \$ потому что последний поиск не выполняется для каждой итерации).
Предлагаемое мной решение:
- Создайте карту / словарь
{value: index}( \$ O(n) \$) - Перебрать
index, valueмассив ( \$ O(n) \$) - Поиск и возврат индекса с карты / dict ( \$ O(1) \$)
def two_sum(numbers: list[int], target: int):
lookup: dict = {
value: index
for index, value in enumerate(numbers)
}
for index, value in enumerate(numbers):
match = target - value
if search_index := lookup.get(match):
return index, search_index
return None
Это интересно мне, потому что я вырос в C и начал использовать Python в последние несколько лет для работы, поэтому у меня был обратный путь, как у вас. Когда я начинал Python, я очень отдавал предпочтение решениям, подобным вашему, потому что циклический просмотр списков настолько ясен и понятен.
Однако с тех пор я узнал, что более опытные программисты Python на работе лучше понимают мой код, когда я использую стандартную библиотеку. Когда я начал вкладывать средства в изучение этих инструментов, это дало двойной эффект: 1) мой код стал более кратким и 2) стал более эффективным во времени и / или пространстве.
В этом случае я бы решил проблему с помощью combinationsиз itertoolsпакета:
from itertools import combinations
def two_sum(nums, target):
pairs_with_indices = combinations(enumerate(nums), 2)
# result is a generator comprehension.
winning_pairs = ((index_i, index_j)
for (index_i, i), (index_j, j) in pairs_with_indices
if sum((i, j)) == target)
# Insert as much error checking as you need...
return next(winning_pairs)
Вероятно, есть еще лучшее, более сжатое и ясное решение с использованием Numpy, который фактически является стандартной библиотекой в моей сфере работы (наука о данных), но это не везде.
Одно отличие от вашего кода: здесь нет места для единичных ошибок. По моему опыту, такой код
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
мне легко писать, трудно читать, а ремонтопригодность охватывает весь путь от простого до невозможного. Другими словами, управление индексами вручную в Python дает мне достаточно веревки, чтобы повеситься, а стандартные библиотечные функции были отличной альтернативой.
Знай свои контейнеры
std::unordered_mapтвой друг в этой проблеме. Если вы никогда раньше не видели число, просто используйте функцию operator[]или, insertчтобы сложить число и его индекс. При использовании findон вернет итератор, который является key-valueпарой.
например: auto location = m.find(numToFind);
location->firstэто ваш ключ и location->secondваша ценность
Когда вы вернетесь, не используйте push_back
Вы можете просто вернуть список инициализации , как: {i,j}.