Esta es la pregunta: https://leetcode.com/problems/contains-duplicate-ii/
Dada una matriz de enteros nums y un entero k, devuelve verdadero si hay dos índices distintos i y j en la matriz tales que nums[i] == nums[j] y abs(i - j) <= k.
Mi código:
var containsNearbyDuplicate = function(nums, k) { for(let i = 0; i < nums.length; i++) { for(let j = i+1; j < nums.length; j++) { console.log([i, j]) if(nums[i] == nums[j] && Math.abs(ij) <= k){ return true; } } } return false; };En el momento de la presentación, puedo pasar 20/51 casos con el estado 'Límite de tiempo excedido'.
Puedo pasar las siguientes entradas de ejemplo:
Ejemplo 1:
Input: nums = [1,2,3,1], k = 3 Output: trueEjemplo 2:
Input: nums = [1,0,1,1], k = 1 Output: trueEjemplo 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: falseNo puedo pensar en ningún caso marginal que esté causando que la presentación exceda el límite de tiempo. Soy consciente de que hay otras formas de resolver este problema, pero me gustaría saber cuál es el problema con mi código.
EDITAR:
Me di cuenta de que el problema está en esta línea: console.log([i, j]). Si lo comento, no hay problema con el envío. Pero no estoy muy seguro de por qué esa línea está causando el error de límite de tiempo excedido.
Leetcode y sitios similares a menudo proporcionan grandes conjuntos de datos como entrada. En tales casos, un algoritmo innecesariamente complejo desde el punto de vista computacional puede requerir demasiado tiempo de procesamiento para completarse. Eso puede ser lo que está pasando aquí.
Tiene un bucle anidado: si la matriz de entrada contiene 1000 elementos, eso es del orden de 1000 * 1000 iteraciones. Use un algoritmo diferente y menos costoso, como iterar sobre la entrada solo una vez. Un enfoque posible es
var containsNearbyDuplicate = function(nums, k) { const numsByLastIndex = {}; for(let i = 0; i < nums.length; i++) { const num = nums[i]; if (numsByLastIndex[num] !== undefined && i - numsByLastIndex[num] <= k) { return true; } numsByLastIndex[num] = i; } return false; };Cuando pruebo el código anterior, el tiempo requerido ha cambiado del orden de 9 segundos (que puede estar cerca del límite) a 1/4 de segundo.
Otro problema es que iniciar sesión en la CLI del nodo, si realiza muchos registros, puede ralentizar las cosas . A veces, el registro puede incluso ocupar la mayor parte del tiempo de procesamiento de su secuencia de comandos. No es necesario para realizar la tarea, así que siéntete libre de eliminarlo.