Leetcode dois soma
No momento, estou aprendendo c ++ vindo de um plano de fundo de python, então incluirei uma solução em python e em c ++ para a seguinte declaração de problema:
Dado um array de números inteiros e um alvo inteiro, retorna os índices dos dois números de forma que eles se somam ao alvo. Você pode presumir que cada entrada teria exatamente uma solução e não pode usar o mesmo elemento duas vezes. Você pode retornar a resposta em qualquer ordem.
Exemplo 1:
Entrada: nums = [2,7,11,15], alvo = 9
Resultado: [0,1]
Exemplo 2:
Entrada: nums = [3,2,4], alvo = 6
Resultado: [1,2]
Gostaria de ouvir seus comentários / sugestões para melhorias de desempenho / outras sugestões. Aqui está o link
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')
Estatísticas Leetcode:
Tempo de execução: 772 ms, mais rápido do que 36,98% dos envios online do Python para Two Sum. Uso de memória: 14,4 MB, menos de 49,82% dos envios online do Python para 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");
}
Estatísticas Leetcode:
Tempo de execução: 384 ms, mais rápido do que 34,03% dos envios online C ++ para Two Sum. Uso de memória: 9,3 MB, menos de 12,99% dos envios online de C ++ para Two Sum.
Respostas
Não sou um especialista em C ++, mas posso dar um feedback sobre a solução Python.
Sua solução atual é executada em \$O(n^2)\$. Basicamente, para cada número nda entrada nums, encontre target - nem nums. Como melhorar isso?
A segunda parte do algoritmo pode ser melhorada em \$O(n)\$para \$O(1)\$. Em vez de procurar target - nem uma lista, você pode usar um dicionário:
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
Resultados:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Inclua apenas os arquivos de cabeçalho de que você precisa
No seu two_sum.harquivo, você não precisa iostream, já que não está usando nenhuma de suas funcionalidades. Lembre-se de que #includeliteralmente copia e cola o arquivo, portanto, se você estiver incluindo este arquivo de cabeçalho em vários arquivos, isso pode diminuir o tempo de compilação.
Declarações e definições de divisão
Normalmente, você dividiria seus arquivos em duas partes: o arquivo de cabeçalho (normalmente terminando com *.h, *.hpp, *.hh) e o arquivo de origem (normalmente terminando com *.cpp, *.cc). O arquivo de cabeçalho consiste apenas nas declarações e o arquivo de origem contém a implementação.
Portanto, no seu caso, o arquivo de cabeçalho terá a seguinte aparência:
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
e seu arquivo de origem terá a seguinte aparência:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
Na verdade, se você tentar incluir seu two_sum.h(com a implementação) em vários arquivos, estará quebrando a Regra de Uma Definição . Seus arquivos de origem conteriam várias definições da mesma função e o vinculador cuspirá um erro. Uma maneira de contornar é marcar as funções inline, mas provavelmente você deseja fazer a primeira.
Não using namespacenos arquivos de cabeçalho
Não faça using namespaceou qualquer uma de suas variantes em um arquivo de cabeçalho. Como o arquivo de cabeçalho é copiado e colado em vários arquivos de origem, ele pode causar erros irritantes. Veja aqui
Use referência const
Como two_sum_solutionnão está modificando o numsvetor, passe-o por referência const.
size_t vs int para índices de matriz
Considere o uso de size_t em vez de int para índices de matriz
Use autoo máximo possível
Existem algumas instâncias em seu código onde você pode usar em autovez de especificar o tipo. Exemplos:
auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);
O loop mais interno é inútil
Simplesmente faça
results.push_back(i);
results.push_back(j);
Além disso, depois de encontrar a solução, você pode querer retornar o resultado imediatamente.
Talvez você possa melhorar o desempenho criando um mapa de valor -> índice na primeira iteração sobre a matriz fornecida.
Atualmente, seu programa faz o seguinte (complexidade de tempo):
- iterar em todos os
index, valuepares da matriz ( \$ O(n) \$) - procurar
target - valuena matriz ( \$ O(n) \$) - índice de pesquisa de
target - value( \$ O(n) \$)
E como todos estão aninhados, você chega a \$ O(n^2) \$(não é \$ n^3 \$ porque a última pesquisa não está sendo feita para cada iteração).
Minha solução proposta:
- Crie um mapa / dicionário de
{value: index}( \$ O(n) \$) - Iterar sobre a
index, valuematriz ( \$ O(n) \$) - Pesquisar e retornar o índice do mapa / 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
Isso é interessante para mim porque eu venho de uma formação em C e comecei a usar Python nos últimos anos para trabalhar, então escolhi o caminho inverso para você. Quando comecei o Python, preferia muito soluções como a sua, porque o loop nas listas é muito explícito e claro.
No entanto, desde então aprendi que os programadores Python mais proficientes no trabalho entendem melhor meu código quando uso a biblioteca padrão. Assim que comecei a investir no aprendizado dessas ferramentas, tive o duplo efeito de 1) tornar meu código mais sucinto e 2) ser mais eficiente no tempo e / ou espaço.
Nesse caso, eu resolveria o problema com combinationsdo itertoolspacote:
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)
Provavelmente existe uma solução ainda melhor, mais sucinta e clara, usando Numpy, que é efetivamente uma biblioteca padrão na minha linha de trabalho (ciência de dados), mas isso não é verdade em todos os lugares.
Uma coisa que é diferente do seu código: não há espaço para erros aleatórios. Na minha experiência, código como este
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
é fácil para mim escrever, difícil de ler e a capacidade de manutenção abrange todo o gambito, do fácil ao impossível. Em outras palavras, gerenciar índices manualmente em Python me dá corda suficiente para me enforcar, e as funções de biblioteca padrão têm sido uma ótima alternativa.
Conheça seus contêineres
std::unordered_mapé seu amigo neste problema. Sempre que você nunca viu um número anteriormente, simplesmente use a função operator[]ou insertpara adicionar o número e seu índice. Ao usar find, ele retornará um iterador, que é um key-valuepar.
por exemplo: auto location = m.find(numToFind);
location->firsté a sua chave e location->secondé o seu valor
Quando você retornar, não use push_back
Você pode simplesmente retornar uma lista de inicializador como: {i,j}.