Estoy tratando de resolver la pregunta Two Sum II - Input Array Is Sorted en leetcode, me está dando Time Limit Exceeded , así que supongo que mi código no está bien optimizado y necesita soluciones más eficientes. Pero no soy tan bueno en eso, así que para ser específico, ¿cómo puedo eliminar dos for-loops con uno en mi código?
Ques1: Two Sum II - Input Array Is Sorted
Dada una matriz de números enteros indexada en 1 que ya está ordenada en orden no decreciente, busque dos números que sumen un número objetivo específico. Sean estos dos números números[índice1] y números[índice2] donde 1 <= índice1 < índice2 <= números.longitud.
Devuelve los índices de los dos números, índice1 e índice2, sumados por uno como una matriz de enteros [índice1, índice2] de longitud 2. Las pruebas se generan de manera que haya exactamente una solución. No puede usar el mismo elemento dos veces. Su solución debe usar solo espacio adicional constante.
Ejemplo:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].enlace de preguntas
Mi código: Casos de prueba 20 / 21
var twoSum = function(numbers, target) { let arr=[]; for(let i=0; i<numbers.length; i++){ let findNum= target - numbers[i]; for(let j=i+1;j<numbers.length; j++){ if(numbers[j]===findNum) arr.push(i+1, j+1); } } return arr };¿Cómo puedo optimizar mi código para que pueda ejecutar todos los casos de prueba?
Puede utilizar el enfoque de dos puntos,
No publicaré la respuesta real porque eso arruinaría la diversión.
Tengo una respuesta para la pregunta 2. Has anidado bucles for. El bucle anidado se ejecutará n - i veces cada vez, donde i varía de 1 a n. Entonces, la complejidad temporal total del código sería (n-1) + (n-2) + ... + 0, que sería (n*(n-1))/2. Esta es una solución de orden O (n ^ 2). En la pregunta n es 3 * 10^4 lo que daría como resultado más de 10^8 operaciones por segundo. Por lo tanto, dará un error de límite de tiempo excedido. Ahora, para resolver esto, puede usar la propiedad de matriz ordenada. Podemos tomar dos punteros, uno al comienzo de la matriz y otro en el último índice. Habría tres casos:
Lo haremos hasta que i no sea igual a j. Aquí está el código completo.
var twoSum = function(numbers, target) { enter code here let ans = []; while(i<j) { if(numbers[i] + numbers[j] > target) { j--; } else if(numbers[i] + numbers[j] < target) { i++; } else { ans.push(i+1); ans.push(j+1); break; } } return ans; };