Solución JavaScript O(n).

 function hasPairsWithSum(array, sum) { const map = new Map (); for(let i = 0; i < array.length; i++) { let currVal = array[i]; if (map.has(currVal)) { return [map.get(currVal),i] } // difference value = sum - current value let diff = sum - currVal map.set(diff,i) } }; console.log(hasPairsWithSum([2,2,4,4], 8))

Debe iterar sobre los elementos de la matriz comprobando en cada iteración cada elemento de la matriz (excepto el último) todos los elementos a la derecha como se muestra a continuación:

 function findIndexes(array, sum) { const result = []; for (let i = 0; i < array.length -1; ++i) { for (let j = i + 1; j < array.length; ++j) { if ((array[i] + array[j]) === sum) { result.push([i, j]); } } } return result; } console.log(findIndexes([1, 2, 4, 4], 8)); console.log(findIndexes([3, 2, 4], 6));

Actualizar:

Es posible obtener una complejidad lineal O(n) utilizando una estructura Map auxiliar asociando un valor entero como clave con un valor de la lista que contiene todos los índices de los elementos en el arreglo igual a la clave entera como se muestra a continuación:

 function findIndexes(array, sum) { const map = new Map(); const result = []; for (let i = 0; i < array.length; ++i) { const a = array[i]; const b = sum - a; if (map.has(b)) { for (const index of map.get(b)) { result.push([index, i]); } } const l = map.has(a) ? map.get(a) : []; l.push(i); map.set(a, l); } return result; } console.log(findIndexes([1, 2, 4, 4], 8)); console.log(findIndexes([3, 2, 4], 6)); console.log(findIndexes([1, 1, 1], 2));

O (n) Soln ... usando el concepto matemático a + b = n, entonces si a está presente en nuestra matriz, entonces necesita encontrar b = n - a está presente o no ...

 def hasPairsWithSum(array,sum): d = {} for i in range(len(array)): if(array[i] in d): d[array[i]].append(i) else: d[array[i]] = [i] ans = [] for i in range(len(array)): val = sum - array[i] if(val in d): if(d[val][0] == i): if(len(d[val]) > 1): ans.append((i,d[val][1])) break else: continue else: ans.append((i,d[val][0])) break return ans print(hasPairsWithSum([4, 4, 4, 4], 8))

O (nlogn) soln ... solo almacene el índice con elementos ... luego ordénelo por sus valores ... el siguiente paso ejecute un ciclo con complejidad de O (n) [concepto: dos punteros]

 def hasPairsWithSum(array,sum): arr = [] for i in range(len(array)): arr.append((array[i],i)) arr.sort() i = 0 j = len(array)-1 ans = [] while(i<j): tmp_sum = arr[i][0] + arr[j][0] if(tmp_sum == sum): ans.append((arr[i][1] , arr[j][1])) #add your logic if you want to find all possible indexes instead of break break elif(tmp_sum < sum): i = i + 1 elif(tmp_sum > sum): j = j - 1 return ans print(hasPairsWithSum([1,2,4,4],8))

• nota: si desea encontrar todas las soluciones posibles, estos enfoques no funcionarán, agregue su propia lógica en el ciclo while u otro enfoque es usar la búsqueda binaria con recorrido en cada elemento y almacenar los índices en el conjunto (en el peor de los casos, será O( n ^ 2) ya que tenemos que encontrar todos los valores posibles) Por ejemplo: [4,4,4,4,4,4] , suma = 8 y desea imprimir todos los índices posibles, luego terminamos ejecutándolo hasta n ^ 2 (¿Por qué? razón: el total de soluciones posibles son 5+4+3+2+1 = n*(n-1)/2 ≈ n^2)