@@williamrosa8577 Canais focados em problemas algoritmicos como esse aqui tem o NeetCode e o Colin Galen (o galen é focado em programação competitiva então é um nivel bem mais avançado de problemas) Canais excelentes sobre matemática e problemas algoritmicos no geral: 3blue1brown Numberphile
não sei se ficou tão claro que um dicionário implementa um hash map **por padrão**. Então quando vc usa um .get(), ele nao percorre o dicionário inteiro procurando o valor, ele gera o hash do item buscado, e consegue responder em O(1) se está lá ou não. Talvez por isso tenha ficado um pouco confuso para algumas pessoas. A simplicidade da linguagem utilizada acabou deixando um descompasso entre a explicação e o código. Não queria desmerecer o vídeo nem nada, ficou incrível, mas achei que um pessoal tivesse ficado perdido por conta disso e achei importante explicar!
Concordo! Seria bacana se ele tivesse proposto solução sem usar métodos da linguagem. Mas acho que sem querer ele deixou essa pra gente mesmo resolver kkkk
to começando a estudar DSA após negligenciar por muito tempo durante minha carreira, já havia resolvido o two sum de maneira super fácil com a solução 1, mas é muito massa encontrar conteúdo como o seu explicando resolução desses problemas do leetcode de maneira otimizada e mostrando a aplicabilidade dos algoritmos e estruturas de dados apropriados
Caraca, essa solução 3 é bem fora da caixinha pra mim. Estou um pouco enferrujado nesse tipo de algoritmo no dia a dia. Vou começar a praticar no Leetcode
A segunda solução tem um problema, quando você dá um sort no array, você modifica os indices dos elementos dele, o que acaba inutilizando o algoritmo por que a resposta vai dar os indices incorretos.
Você pode manter o vetor original inalterado e criar uma cópia ordenada dele para fazer a busca. Depois basta procurar a posição dos elementos da solução no vetor original (o que mantém a complexidade temporal de nlogn). Problema disso: armazenamento de 2n elementos na memória.
Da pra achar o valor Vc normalmente reatribui o nums.sort pra uma nova var Ou usa ele já em um loop De qualquer forma, você consegue buscar o índice na lista de vários jeitos O problema é que Aumenta a complexidade o que na minha opinião faria ela a pior solução
@@leonardomiguel1943mas a hash dele tbm faz isso. Cria uma copia (ate maior, pq armazena chave e valor) do "banco de dados" na memória (pensando num cenário com muito mais dados)
@@leonardomiguel1943 o problema é que pra vc procurar a posição dos elementos no array original seria O(n), não? pq se o array não esta ordenado, não teria como fazer uma busca binaria, por ex.
@@gabrielcarvalho9156 não pensei muito à fundo mas a princípio, O(n) é bom. Essa busca não aumentaria a complexidade. Buscar cada um poderia gerar um trabalhinho a mais, mas em termos de complexidade se manteria O(nlogn)
Eu pensei na última solução, por causa do x + y = 9, e o x = 9 - y. Entretanto, usei o try para tentar acessar o index da lista, arr.index(x), invés de armazenar tudo em um dicionário. Problema bem legal, que o conhecimento mais básico em sistemas lineares já dá uma ajuda.
Fui inventar de fazer esse exercício dps de ver esse vídeo, continueo com dificuldade e tive que ver denovo KASOEKOASKOEKOASEKOASOK programar é uma das coisas existentes
Se o array já tiver ordenado a melhor solução é o two pointers. Mas com o array não ordenado, a melhor solução realmente é com hash map. Muito boa sua explicação 🎉
@@magichatake te dizer que esse relato tirou um pouco de peso na minha consciência, estava me sentindo um merda porque não fazia a mínima ideia de como resolver isso
resolvi isso esses dias na faculdade hshshakdjw. foi na força bruta. extremamente inteligente essa ultima solução, mas precisa pensar um pouco fora da caixa. preciso entender melhor esse assunto de complexidade dos algoritmos. Recomenda algum livro/conteúdo online?
Eu pensei em fazer a primeira solução bruta, verificando antes se o valor do array é maior que nove. Mas dps percebi q só funcionaria se na questão ele garantisse que só teria numeros positivos. Muito legal as outras soluções, aprendi algo aqui hoje.
A soluçao 3 é bem legal, mas tbm tem que considerar que ela copia toda a array, dobrando o armazenamento (pensando em um banco bem maior). Considerando isso, achei a soluçao 2 mais otimizada.
Augusto, você poderia fazer um exemplo assim, mas com valores reais de um possível sistema, tipo nome, cpf, endereço, idade... Porque tipo, fica muito abstrato apenas números. Estou iniciando na programação e gostaria de entender, onde essa solução na prática ajudaria em um "possível" sistema. Agradeço, desde já! =D
Então, questões de leetcode são para sistemas que necessitam de maior performance. Em um geral, sistemas comuns que tudo que fazem é cadastrar dados em um lugar e mostrar em outro nunca vão precisar implementar algo do tipo. eu trabalho com engenharia de dados e recentemente precisei fazer um sistema de cálculo que precisava percorrer por petabytes de informação para conseguir fazer algumas operações, nesse caso esses conceitos me foram uteis pq criei estrutura de dados que organiza os dados que eu vou precisar para aquelas operações de maneira que fica muito mais rápido de acessar
irmão, parabens pelo seu conteudo diferenciado? vc acha que progredir no livro Cormen : introduction to algorithms , iria me ajudar nesse aspecto, ou é mais ficar praticando e batendo cabeça em leetcode, exercism(no caso de aprender uma linguagem nvoa)? tens algum livro ou algum material que te ajudaram qd vc ainda não tinha essa base sólida. Sou Dev frontend(2 anos de xp), me aprofundando em back e querendo aprimorar essa parte de lógica
O que acha de primeiro retirarmos os elementos maiores que o Target e depois aplicar a melhor solução? Acho que isso depende também do tamanho do nosso array inicial né (Sou apenas um estagiário curioso)
Percorrer toda a array e criar uma array intermediária (para positivos não é possível a soma de 2 inteiros dar nove para números maiores ou iguais a 9) no caso de números positivos não seria interessante? A última abordagem é muito boa para casos de uso geral, aí funcionaria se a array problema tivesse números negativos ou estou equivocado?
achei a opcao 2 paia pro leetCode em si, pq ele tem os resultados exatos la ja. quando muda o array o resultado vai mudar consequentemente, teria que percorrer a lista inicial mais uma vez pra saber a posição correta dos valores
Putz, resolvi esse exercício com força bruta, na preguiça fui ver a melhor solução nas respostas da comunidade, li essa solução 3 mas não entendi... até chegar nesse vídeo, agora tá desenhado, valeu kkkk
Eu como programador iniciante faria a "força bruta inteligente" eu só iria calcular os números q são menor q o target, não faz sentido calcular um número q é maior.
É interessante ver as soluções, mas no dia a dia é tão útil quanto um cinzeiro numa moto. No primeiro projeto em equipe ninguém liga se vc resolveu 0 ou 138923 exercícios numa plataforma, parem de viajar.
Iniciante em programação aqui. Cara! Como você consegue chegar na logica da última solução, para mim, o nível de abstração é gigante. Explicação top cara! Qual programa você usa para fazer?
De cara um iniciante realmente não chega nessa lógica, mas se vc quiser ficar bom e algoritmos e pensar fora da caixinha, tem que começar a resolver esses desafios, achar a solução sem pesquisar, e depois buscar uma forma de melhorar ela. Com o tempo vc vai ficando bom
É bem difícil na verdade, mas com mta prática e com um bom conhecimento sobre estrutura de dados é possível. Mas quase ngm cheguem chega nesse tipo de solução de primeira. É normal vc pensar em soluções mais simples, como a primeira q ele mostrou. Quando vc faz isso vc entende melhor o problema, consegue criar abstrações para soluções mais otimizadas
Eu discordo completamente do cara que falou que precisa pensar fora da caixa, todas questões usam ferramentas comuns Se você fizer muitas questões de leetcode você vai começar a identificar padrões e saber qual a melhor ferramenta/estratégia para resolver aquele problema. Ninguém quer que você crie um novo paradigma de programação em tempo real
@@CarloskyppConcordo, Carlos. Só uma observação: o leetcode é mais manjado em geral, mas acredito que para exercícios ad hoc não se aplique. Coisas como teoria dos jogos também, esquece. Ademais, um exercício é realmente difícil quando mesmo quem conhece os paradigmas e algoritmos usados tem dificuldade de enxergar a solução. Caso contrário, bastaria ser uma enciclopedia.
Utilizar hashmap é mais otimizado que utilizar um array simples? Penso que pelo algoritmo de busca do hashmap ele pode ser mais ótimo em certos casos. Mas nesse exemplo em específico a busca em array ganha, não? Já que o tamanho máximo do array será length - 1 sempre
Oi amigo tudo bem? Não sou ele mas vou tentar ajudar. O que importa em big O eh a escala, o length que tu mencionou, tu não sabe quantos elementos pode ser, então pensa que se for um array e tu buscar o array, sempre q tu buscar vai ser O(n). Como tu está buscando dentro de um for, N*N eh O(N^2). O uso de HashMap eh bom porque buscar elementos no HashMap tem acesso constante, eh O(1), logo tu terá só o N do for em si
Não entendi bem a última linha do código, principalmente a sintaxe: hasher[target-i] = idx Entendo que ele precisa fazer a comparação e armazenar no dicionário junto com o index da lista "nums" mas a sintaxe ficou confusa. Hasher é um dicionário, porque usou [ ] e não { }? E porque estamos atribuindo esse valor ao "idx" do for loop do "nums"? Pq isso não interfere no loop? Bugou minha mente total. Se alguém puder ajudar, agradeceria bastante kkkk joguei no chatgpt e ele reescreveu o código dizendo que estava errado, mas sei que não está.
Opa, William! Tudo certo?! Vou tentar esclarecer as dúvidas, qualquer coisa, volte a falar. [NOTA]: Só para deixar claro, a linguagem utilizada para resolução do exercício é Python. 1 - Sobre a variável 'hasher' : Você está correto! Ela é um dicionário. Você consegue atestar isso pela sua inicialização (hasher = {}). O que está ocorrendo na última linha é o povoamento do dicionário, e, só se chagará nela caso a soma pretendida ainda não tiver sido encontrada (isso precisa estar claro, se não estiver, reveja os trechos iniciais do vídeo que explicam a lógica de resolução pelo terceiro método)! "... porque usou [ ] e não { }?" O dicionário é uma estrutura de dados indexada pelo par 'chave-valor' e, para atribuir um novo valor a uma chave de um dicionário, fazemos assim: 'nome_do_dict[chave] = valor'; É por respeito a essa sintaxe que ele utiliza colchetes ([]) na última instrução, e não chaves ({}) - Está atribuíndo o valor 'idx' (índice do complemento), a chave 'target - i' (complemento que falta para somar 9). 2 - Sobre a iteração : É MUITO importante entender que o loop não acontece diretamente sobre a lista 'nums', mas sim sobre uma pequena modificação da mesma. Note que o laço 'for' está atrelado ao retorno de uma função aplicada a 'nums', chamada de 'enumerate()'. Resumidamente, o que essa função faz é: para cada valor presente na lista a qual foi aplicada (nesse caso, 'nums'), haverá o posicionamento de um índice, de modo que, esse par/tupla (índice, valor) será adicionado a uma nova lista (uma lista ENUMERADA). Agora, é preciso saber que, por padrão, o 'for' do Python atua como um 'for each', de modo que para cada laço/iteração sobre a lista retornada por 'enumerate', estamos guardando o conteúdo do ÍNDICE em 'idx' e do VALOR em 'i'. "E porque estamos atribuindo esse valor ao "idx" do for loop do "nums"? Pq isso não interfere no loop?" Veja, em nenhum momento há atribuição de um novo valor a 'idx', e sim o contrário: o índice 'idx' é atribuído a uma determinada chave (target-i) do dicionário 'hasher'. De nenhuma forma, alteramos diretamente a lista "nums". Sei que a explicação está grande, e talvez um pouco confusa. Mas espero ter conseguido ajudar de alguma forma! Abraço!
com 50ms: class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hasher={} for i in range(len(nums)): if nums[i] in hasher.keys(): return [i, hasher[nums[i]]] else: hasher[target - nums[i]] = i
A melhor solução é iterar pela lista e precomputar qual número somado ao elemento atual da lista é igual ao alvo (target). Isso evita você ter que iterar a lista multiplas vezes pra procurar qual número somado dá o alvo. Por isso é a melhor solução, complexidade O(N) (Big O de N, o tempo de execução no pior caso é proporcional ao tamanho da lista, N)
isso é a coisa mais inútil do mundo pra medir a habilidade de um desenvolvedor, desenvolver envolve MUITA COISA, um cara ruim que apenas estudar as principais questoes de algoritmo e ficar bom em algoritmo, ainda está longe de ser capaz de desenvolver softwares escaláveis, de qualidade e etc. um cara com experiência e sem treino de algoritmo, é muito mais fácil desenrolar uma tarefa que precise de um algoritmo complexo (nao é esse o caso) do que o contrário. se quiser passar em entrevista, infelizmente tem que treinar esses algoritmo inúteis pra depois em 99% do trabalho não precisar deles. Foda, mercado deixa de pegar muita gente excelente por causa disso
@@powersamurai686 Opa! São notações BigO, a gente usa pra determinar se, pra chegar em um resultado, um algoritmo passaria muitas ou poucas vezes por um determinado ponto (no caso o ponto é acessar um valor no array), ou seja, se os loops vão acabar rápido ou não kkk. O O(log n) significa que você vai acessar uma fração relativa ao tamanho do input - no caso o input é [2, 7, 11, 15], e se o input pedisse pra somar a primeira metade do array com a segunda, daria pra fazer com O(log n) e o resultado seria [13, 22]; O O(n log n) significa que você vai acessar essa mesma fração mas para cada item do array - que seria procurar pra cada item um par no array que desse o resultado esperado, caso não fique claro usando o exercício do vídeo, tenta trocar a ordem dos itens que vai ajudar; O O(n) significa que você vai necessariamente passar por todos os items do array - tipo se vc precisar somar o array todo ou algo assim; O O(1) significa que praticamente não vai ter loop! tem outros tmbm, mas a ideia é por aí
Conteúdo top Augusto, caramba, que massa encontrar alguém que ajude a comunidade dessa maneira por aqui no YT!
No Brasil né, realmente excelente o conteúdo. A altura do da gringa
@@AndrePaganottoverdade demais isso aí. O conteudo aqui do Brasil geralmente são coisas muito básicas ou cara tentando vender curso.
@@AndrePaganotto Tem recomendações de canais gringos que fazem esse tipo de conteúdo?
@@williamrosa8577
Canais focados em problemas algoritmicos como esse aqui tem o NeetCode e o Colin Galen (o galen é focado em programação competitiva então é um nivel bem mais avançado de problemas)
Canais excelentes sobre matemática e problemas algoritmicos no geral:
3blue1brown
Numberphile
@@AndrePaganotto Obrigado!
não sei se ficou tão claro que um dicionário implementa um hash map **por padrão**.
Então quando vc usa um .get(), ele nao percorre o dicionário inteiro procurando o valor, ele gera o hash do item buscado, e consegue responder em O(1) se está lá ou não.
Talvez por isso tenha ficado um pouco confuso para algumas pessoas.
A simplicidade da linguagem utilizada acabou deixando um descompasso entre a explicação e o código.
Não queria desmerecer o vídeo nem nada, ficou incrível, mas achei que um pessoal tivesse ficado perdido por conta disso e achei importante explicar!
Concordo! Seria bacana se ele tivesse proposto solução sem usar métodos da linguagem. Mas acho que sem querer ele deixou essa pra gente mesmo resolver kkkk
to começando a estudar DSA após negligenciar por muito tempo durante minha carreira, já havia resolvido o two sum de maneira super fácil com a solução 1, mas é muito massa encontrar conteúdo como o seu explicando resolução desses problemas do leetcode de maneira otimizada e mostrando a aplicabilidade dos algoritmos e estruturas de dados apropriados
Caraca, essa solução 3 é bem fora da caixinha pra mim. Estou um pouco enferrujado nesse tipo de algoritmo no dia a dia. Vou começar a praticar no Leetcode
A segunda solução tem um problema, quando você dá um sort no array, você modifica os indices dos elementos dele, o que acaba inutilizando o algoritmo por que a resposta vai dar os indices incorretos.
Você pode manter o vetor original inalterado e criar uma cópia ordenada dele para fazer a busca. Depois basta procurar a posição dos elementos da solução no vetor original (o que mantém a complexidade temporal de nlogn). Problema disso: armazenamento de 2n elementos na memória.
Da pra achar o valor
Vc normalmente reatribui o nums.sort pra uma nova var
Ou usa ele já em um loop
De qualquer forma, você consegue buscar o índice na lista de vários jeitos
O problema é que
Aumenta a complexidade o que na minha opinião faria ela a pior solução
@@leonardomiguel1943mas a hash dele tbm faz isso. Cria uma copia (ate maior, pq armazena chave e valor) do "banco de dados" na memória (pensando num cenário com muito mais dados)
@@leonardomiguel1943 o problema é que pra vc procurar a posição dos elementos no array original seria O(n), não? pq se o array não esta ordenado, não teria como fazer uma busca binaria, por ex.
@@gabrielcarvalho9156 não pensei muito à fundo mas a princípio, O(n) é bom. Essa busca não aumentaria a complexidade. Buscar cada um poderia gerar um trabalhinho a mais, mas em termos de complexidade se manteria O(nlogn)
Parabéns pelo seu conteúdo 👏👏👏👏
Obrigado por nós compartilhar
Eu pensei na última solução, por causa do x + y = 9, e o x = 9 - y.
Entretanto, usei o try para tentar acessar o index da lista, arr.index(x), invés de armazenar tudo em um dicionário.
Problema bem legal, que o conhecimento mais básico em sistemas lineares já dá uma ajuda.
Cara, obrigado por dedicar um tempo a nos explicar isso!
Augusto, quando que você vai lançar seu curso de Estrutura de Dados? Você é brabo!
Fui inventar de fazer esse exercício dps de ver esse vídeo, continueo com dificuldade e tive que ver denovo KASOEKOASKOEKOASEKOASOK
programar é uma das coisas existentes
Se o array já tiver ordenado a melhor solução é o two pointers. Mas com o array não ordenado, a melhor solução realmente é com hash map. Muito boa sua explicação 🎉
Super simples -> demorei 2 semanas para fazer e ainda tive que ver tutorial de indiano na net
kkkk tbm to nessas mano... e olha q to há 8 anos já na area, essas coisas de algoritmo sempre me pegam
Só um indiano fez isso sem consultar outro indiano
@@magichatake te dizer que esse relato tirou um pouco de peso na minha consciência, estava me sentindo um merda porque não fazia a mínima ideia de como resolver isso
resolvi isso esses dias na faculdade hshshakdjw. foi na força bruta. extremamente inteligente essa ultima solução, mas precisa pensar um pouco fora da caixa. preciso entender melhor esse assunto de complexidade dos algoritmos. Recomenda algum livro/conteúdo online?
pra introdução aquele “entendendo algoritmos” é muito bom, ele mostra uns conceitos e algoritmos bem interessantes de forma simples
Procura sobre analise assintótica, aqui no youtube tem videos sobre que explicam toda essa área de análise e complexidade de algoritmos
obrigado, senhores 🔥
Eu pensei em fazer a primeira solução bruta, verificando antes se o valor do array é maior que nove. Mas dps percebi q só funcionaria se na questão ele garantisse que só teria numeros positivos. Muito legal as outras soluções, aprendi algo aqui hoje.
A soluçao 3 é bem legal, mas tbm tem que considerar que ela copia toda a array, dobrando o armazenamento (pensando em um banco bem maior).
Considerando isso, achei a soluçao 2 mais otimizada.
me sinto burro vendo seus videos KKK cara tu e muito foda slk
pra mim qualquer coisa de algoritmo me faz me sentir burro
Augusto, você poderia fazer um exemplo assim, mas com valores reais de um possível sistema, tipo nome, cpf, endereço, idade... Porque tipo, fica muito abstrato apenas números. Estou iniciando na programação e gostaria de entender, onde essa solução na prática ajudaria em um "possível" sistema. Agradeço, desde já! =D
Então, questões de leetcode são para sistemas que necessitam de maior performance. Em um geral, sistemas comuns que tudo que fazem é cadastrar dados em um lugar e mostrar em outro nunca vão precisar implementar algo do tipo.
eu trabalho com engenharia de dados e recentemente precisei fazer um sistema de cálculo que precisava percorrer por petabytes de informação para conseguir fazer algumas operações, nesse caso esses conceitos me foram uteis pq criei estrutura de dados que organiza os dados que eu vou precisar para aquelas operações de maneira que fica muito mais rápido de acessar
irmão, parabens pelo seu conteudo diferenciado? vc acha que progredir no livro Cormen : introduction to algorithms , iria me ajudar nesse aspecto, ou é mais ficar praticando e batendo cabeça em leetcode, exercism(no caso de aprender uma linguagem nvoa)? tens algum livro ou algum material que te ajudaram qd vc ainda não tinha essa base sólida. Sou Dev frontend(2 anos de xp), me aprofundando em back e querendo aprimorar essa parte de lógica
Muito bom, gosto muito dos seus vídeos
Obrigado pelo conteúdo e pelas dicas
Cabra inoxidável da peste, [Rapaz brilhante!] Oh raios, os recrutadores vão tirar esse teste da grade ahhahahah
Massa demais. A primeira solução que sempre vem a mente é brute force 😂
O que acha de primeiro retirarmos os elementos maiores que o Target e depois aplicar a melhor solução? Acho que isso depende também do tamanho do nosso array inicial né (Sou apenas um estagiário curioso)
Isso só incrementa uma percorrida inteira no array
pra fazer isso vc teria que ou percorrer uma vez inteira o vetor a mais ou ordenar ele
de qualquer dos jeitos fica mais caro
Que video Topppp! Qual programa você usa para explicar?
Percorrer toda a array e criar uma array intermediária (para positivos não é possível a soma de 2 inteiros dar nove para números maiores ou iguais a 9) no caso de números positivos não seria interessante? A última abordagem é muito boa para casos de uso geral, aí funcionaria se a array problema tivesse números negativos ou estou equivocado?
achei a opcao 2 paia pro leetCode em si, pq ele tem os resultados exatos la ja. quando muda o array o resultado vai mudar consequentemente, teria que percorrer a lista inicial mais uma vez pra saber a posição correta dos valores
Putz, resolvi esse exercício com força bruta, na preguiça fui ver a melhor solução nas respostas da comunidade, li essa solução 3 mas não entendi... até chegar nesse vídeo, agora tá desenhado, valeu kkkk
Legal, eu fiz antes de ver o vídeo bem rapidinho e a solução do vídeo foi melhor que a minha 😂
Eu como programador iniciante faria a "força bruta inteligente" eu só iria calcular os números q são menor q o target, não faz sentido calcular um número q é maior.
Poderia usar um hashset ao invés do hashmap também, eu acho
É interessante ver as soluções, mas no dia a dia é tão útil quanto um cinzeiro numa moto.
No primeiro projeto em equipe ninguém liga se vc resolveu 0 ou 138923 exercícios numa plataforma, parem de viajar.
fantástico!
Iniciante em programação aqui.
Cara! Como você consegue chegar na logica da última solução, para mim, o nível de abstração é gigante. Explicação top cara! Qual programa você usa para fazer?
De cara um iniciante realmente não chega nessa lógica, mas se vc quiser ficar bom e algoritmos e pensar fora da caixinha, tem que começar a resolver esses desafios, achar a solução sem pesquisar, e depois buscar uma forma de melhorar ela. Com o tempo vc vai ficando bom
@@LeviCacau prática é tudo né
É bem difícil na verdade, mas com mta prática e com um bom conhecimento sobre estrutura de dados é possível.
Mas quase ngm cheguem chega nesse tipo de solução de primeira. É normal vc pensar em soluções mais simples, como a primeira q ele mostrou. Quando vc faz isso vc entende melhor o problema, consegue criar abstrações para soluções mais otimizadas
Eu discordo completamente do cara que falou que precisa pensar fora da caixa, todas questões usam ferramentas comuns
Se você fizer muitas questões de leetcode você vai começar a identificar padrões e saber qual a melhor ferramenta/estratégia para resolver aquele problema. Ninguém quer que você crie um novo paradigma de programação em tempo real
@@CarloskyppConcordo, Carlos. Só uma observação: o leetcode é mais manjado em geral, mas acredito que para exercícios ad hoc não se aplique. Coisas como teoria dos jogos também, esquece.
Ademais, um exercício é realmente difícil quando mesmo quem conhece os paradigmas e algoritmos usados tem dificuldade de enxergar a solução. Caso contrário, bastaria ser uma enciclopedia.
Utilizar hashmap é mais otimizado que utilizar um array simples? Penso que pelo algoritmo de busca do hashmap ele pode ser mais ótimo em certos casos. Mas nesse exemplo em específico a busca em array ganha, não? Já que o tamanho máximo do array será length - 1 sempre
Oi amigo tudo bem? Não sou ele mas vou tentar ajudar.
O que importa em big O eh a escala, o length que tu mencionou, tu não sabe quantos elementos pode ser, então pensa que se for um array e tu buscar o array, sempre q tu buscar vai ser O(n). Como tu está buscando dentro de um for, N*N eh O(N^2).
O uso de HashMap eh bom porque buscar elementos no HashMap tem acesso constante, eh O(1), logo tu terá só o N do for em si
Por baixo dos panos acho q o complicador cria um array mesmo, então o acesso no hashmap deve ser O(1)
Mano, hashmap é, na maioria das vezes, a melhor coisa pq ele aponta para o elemento na memória sem ter que procurar (fzr um "loop" até achar)
A lógica nem é tão complexa assim
Video muito bom!!!
Não entendi bem a última linha do código, principalmente a sintaxe:
hasher[target-i] = idx
Entendo que ele precisa fazer a comparação e armazenar no dicionário junto com o index da lista "nums" mas a sintaxe ficou confusa. Hasher é um dicionário, porque usou [ ] e não { }? E porque estamos atribuindo esse valor ao "idx" do for loop do "nums"? Pq isso não interfere no loop? Bugou minha mente total.
Se alguém puder ajudar, agradeceria bastante kkkk joguei no chatgpt e ele reescreveu o código dizendo que estava errado, mas sei que não está.
Opa, William! Tudo certo?! Vou tentar esclarecer as dúvidas, qualquer coisa, volte a falar.
[NOTA]: Só para deixar claro, a linguagem utilizada para resolução do exercício é Python.
1 - Sobre a variável 'hasher' : Você está correto! Ela é um dicionário. Você consegue atestar isso pela sua inicialização (hasher = {}). O que está ocorrendo na última linha é o povoamento do dicionário, e, só se chagará nela caso a soma pretendida ainda não tiver sido encontrada (isso precisa estar claro, se não estiver, reveja os trechos iniciais do vídeo que explicam a lógica de resolução pelo terceiro método)!
"... porque usou [ ] e não { }?"
O dicionário é uma estrutura de dados indexada pelo par 'chave-valor' e, para atribuir um novo valor a uma chave de um dicionário, fazemos assim: 'nome_do_dict[chave] = valor'; É por respeito a essa sintaxe que ele utiliza colchetes ([]) na última instrução, e não chaves ({}) - Está atribuíndo o valor 'idx' (índice do complemento), a chave 'target - i' (complemento que falta para somar 9).
2 - Sobre a iteração : É MUITO importante entender que o loop não acontece diretamente sobre a lista 'nums', mas sim sobre uma pequena modificação da mesma. Note que o laço 'for' está atrelado ao retorno de uma função aplicada a 'nums', chamada de 'enumerate()'.
Resumidamente, o que essa função faz é: para cada valor presente na lista a qual foi aplicada (nesse caso, 'nums'), haverá o posicionamento de um índice, de modo que, esse par/tupla (índice, valor) será adicionado a uma nova lista (uma lista ENUMERADA).
Agora, é preciso saber que, por padrão, o 'for' do Python atua como um 'for each', de modo que para cada laço/iteração sobre a lista retornada por 'enumerate', estamos guardando o conteúdo do ÍNDICE em 'idx' e do VALOR em 'i'.
"E porque estamos atribuindo esse valor ao "idx" do for loop do "nums"? Pq isso não interfere no loop?"
Veja, em nenhum momento há atribuição de um novo valor a 'idx', e sim o contrário: o índice 'idx' é atribuído a uma determinada chave (target-i) do dicionário 'hasher'. De nenhuma forma, alteramos diretamente a lista "nums".
Sei que a explicação está grande, e talvez um pouco confusa. Mas espero ter conseguido ajudar de alguma forma! Abraço!
Eu tava pensando, ahh dá uma variável pra ele e faz um print(variavel[2]+variavel[3])
Mas pensei, ele vai desconsiderar...
muito top
com 50ms:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hasher={}
for i in range(len(nums)):
if nums[i] in hasher.keys():
return [i, hasher[nums[i]]]
else:
hasher[target - nums[i]] = i
Qual a linguagem que foi utilizada nesse vídeo? (na parte final)
python
Não consegui entender :(
A melhor solução é iterar pela lista e precomputar qual número somado ao elemento atual da lista é igual ao alvo (target). Isso evita você ter que iterar a lista multiplas vezes pra procurar qual número somado dá o alvo. Por isso é a melhor solução, complexidade O(N) (Big O de N, o tempo de execução no pior caso é proporcional ao tamanho da lista, N)
Obrigado @heraldolucena623
Qual a complexidade do metodo '.get()'? Isso não deveria ser levado em conta?
É O(1). Tem que ser levado em conta sim. Por exemplo, se .get() fosse O(n) ai o algoritmo ficava O(n2)
@@GutoGalego show de bola Augusto, obrigado!!
isso é a coisa mais inútil do mundo pra medir a habilidade de um desenvolvedor, desenvolver envolve MUITA COISA, um cara ruim que apenas estudar as principais questoes de algoritmo e ficar bom em algoritmo, ainda está longe de ser capaz de desenvolver softwares escaláveis, de qualidade e etc.
um cara com experiência e sem treino de algoritmo, é muito mais fácil desenrolar uma tarefa que precise de um algoritmo complexo (nao é esse o caso) do que o contrário.
se quiser passar em entrevista, infelizmente tem que treinar esses algoritmo inúteis pra depois em 99% do trabalho não precisar deles.
Foda, mercado deixa de pegar muita gente excelente por causa disso
1:47 ela seria n/2 + n log n, não? pq percorreria metade do array
mano me explica pf oq eu seria isso de "O de N ou N log N, brisei nessa parte"
@@powersamurai686 Opa! São notações BigO, a gente usa pra determinar se, pra chegar em um resultado, um algoritmo passaria muitas ou poucas vezes por um determinado ponto (no caso o ponto é acessar um valor no array), ou seja, se os loops vão acabar rápido ou não kkk.
O O(log n) significa que você vai acessar uma fração relativa ao tamanho do input - no caso o input é [2, 7, 11, 15], e se o input pedisse pra somar a primeira metade do array com a segunda, daria pra fazer com O(log n) e o resultado seria [13, 22];
O O(n log n) significa que você vai acessar essa mesma fração mas para cada item do array - que seria procurar pra cada item um par no array que desse o resultado esperado, caso não fique claro usando o exercício do vídeo, tenta trocar a ordem dos itens que vai ajudar;
O O(n) significa que você vai necessariamente passar por todos os items do array - tipo se vc precisar somar o array todo ou algo assim;
O O(1) significa que praticamente não vai ter loop!
tem outros tmbm, mas a ideia é por aí
@@williansteinagel valeu pela explicação, tava vendo um video pra entender e sua explicação complementou para o meu entendimento, valeuu!