Problema de duas soma em python
Resolvendo dois problemas de soma em python
Sua abordagem para este tópico será determinada pelo seu nível de especialização. Um método é percorrer a lista, comparando cada item com o resto. Vamos passar por duas técnicas diferentes que você pode usar para remediar este problema.
Declaração de problemas: Retorne todos os pares de dois números cuja soma é igual a um determinado alvo de uma variedade de inteiros. Você pode assumir que cada entrada tem apenas uma resposta racional e que o mesmo elemento não pode ser reutilizado.
Vamos começar explicando a declaração do problema e depois passar para as possíveis soluções. Isso realmente significa que precisamos construir uma função para verificar se existem valores nesta matriz que somam o número de destino fornecido. Forneceremos um exemplo básico para descrever o problema e a solução.
Suponha que recebemos os números [4, 6, 1, -5, 8], e a soma alvo foi 9. Queremos ver se essa matriz tem um par de números que adicionam à soma do alvo fornecido. Como você pode ver, o procedimento deve retornar 8 e 1, que somam até 9 como o total desejado. Então, qual é a melhor estratégia para lidar com este problema? Consulte as seções a seguir:
Solução 1:
A primeira resposta que vem à mente é repetir o loop duas vezes. A técnica nativa usa dois para loops e viaje por toda a matriz duas vezes para atingir a soma pretendida.
Então, passávamos pela matriz um de cada vez. Dessa maneira, você precisa verificar o restante da matriz para saber se a soma é igual ao valor do número especificado ao passar por todos os números.
Por exemplo, podemos continuar com 4 e trabalhar nosso caminho durante o restante dos números [6, 1, -5, 8] para determinar se a adição de 4 a qualquer um deles fornece 9 ou não. Vamos passar para o próximo número, 6, e verificar os números da mesma forma [1, -5, 8] para ver se a adição do número 6 a qualquer um dos números apresentados na matriz fornece 9, antes de continuar o processo através da matriz. O código python para um problema de duas soma com dois para loops é mostrado abaixo.
Def twosumprob (my_arr, t_sum):para i em range (len (my_arr) -1):
para j em range (i, len (my_arr)):
Se my_arr [i]+my_arr [j] == t_sum:
retornar (my_arr [i]. my_arr [j])
retornar[]
A idéia é destacar que, ao mesmo tempo, pode não ser o uso mais eficiente do tempo. Ainda é uma opção viável. Dois para loop resultarão na complexidade do tempo O (n2), pois viajar duas vezes utilizando dois para o loop significaria atravessar o tempo N2 em termos de complexidade do tempo. Como não estamos armazenando nenhum número inteiro, a complexidade do espaço é O (1).
A segunda solução é um método de classificação. Embora o método possa ocupar mais espaço, é mais eficiente sem dúvida.
Solução 2:
Utilizaremos o algoritmo de classificação dessa maneira, já que a classificação requer etapas de tempo nlog (n), que são consideravelmente mais eficientes que o O (n2), empregado na estratégia anterior com dois para loops.
Os números da matriz são classificados primeiro nesta abordagem. Teremos dois ponteiros, um à esquerda no primeiro número da matriz e o outro à direita no último número da matriz.
Simplificaremos esse problema novamente usando o exemplo da matriz anterior de [4, 6, 1, -5, 8]. Os dados são então classificados para refletir uma variedade classificada de [-5, 1, 4, 6, 8]. Nosso ponteiro esquerdo (indicado como l_pointer) será definido como -5 e nosso ponteiro direito (indicado como r_pointer) para 8. Vamos ver se -5 + 8 é igual a 9, que é o total especificado. Não, porque 3 é menor que a soma declarada de 9. Vamos mudar nosso cursor em ordem ascendente, da esquerda para a direita.
Agora, vamos voltar para 1 e ver se a adição de 1 e 8 é igual a 9, o que faz. Isso nos dá o par que estamos procurando. Os pares 1 e 8 agora serão impressos como os pares que fornecerão as duas somas numéricas necessárias.
Vamos falar sobre esta questão um pouco mais. Considere o seguinte cenário: Se a soma alvo for dez e a soma de um e oito for menor que dez, o ponteiro esquerdo será movido para quatro em ordem ascendente. O total de 4 e 8 é igual a 12, que é maior que o total do objetivo.
Como resultado, mudaremos o ponteiro certo em ordem decrescente da posição direita para a esquerda. O ponteiro esquerdo está agora em 4, enquanto o ponteiro certo se mudou para 6. Nesta situação, chegamos ao par de 4 e 6 necessários, o que nos dará a quantidade necessária de 10. O código Python a seguir mostra como as informações anteriores são implementadas abaixo:
Def twosumprob (my_arr, t_sum):my_arr.organizar()
l_pointer = 0
r_pointer = len (my_arr) -1
enquanto l_pointer < r_pointer:
c_sum = my_arr [l_pointer]+my_arr [r_pointer]
se c_sum == t_sum:
return (my_arr [l_pointer], my_arr [r_pointer])
elif c_sum
outro:
r_pointer- = 1
retornar[]
Utilizamos o O (nLogn) em termos de complexidade do tempo devido à classificação, o que é melhor que o método da solução anterior, e é um pouco mais caro porque usa o (nLogn).
Conclusão:
Neste artigo, examinamos o conhecido problema do Python Two Sum e oferecemos duas soluções viáveis para você considerar. Adicionamos duas soluções para corrigir esse problema de duas soma em Python. Esses exemplos podem ser aplicados de maneiras diferentes conforme as necessidades do usuário. Esperamos que você tenha encontrado um artigo útil. Confira outros artigos de dica do Linux para obter mais dicas e informações.