Two Sum, entendiendo el problema

Consiste en encontrar dos números dentro de un arreglo que sumen un valor objetivo específico. En este blog mostraremos la manera brute force para encontrarlo. Nos enfocaremos en lo sencillo.

El Brute Force como tecnica

Existen muchas variantes para resolver esto, abundaremos en Brute Force que es una tecnica sencilla, que hace?:

• Recorre todos los pares posibles del arreglo con dos bucles anidados.
• Para cada par (i, j) verifica si la suma es igual al objetivo.
• No usa ninguna estructura adicional para optimizar la búsqueda.

Complejidad: O(n²) por el doble ciclo.

Descripcion de Two Sum

Te proveen un arreglo de numeros enteros (int) llamado nums y un int llamado target. Target tendra un numero, ese numero es el que debemos buscar en los indices del arreglo. Se informa que cada entrada tendra una solucion y no puedes usar el mismo elemento dos veces.
Ejemplo:

• Input: nums = [2,7,11,15], target = 9
  Aqui se nos indica el arreglo con sus valores. Ese numero 9 es el que buscaremos sumando los indices del arreglo.

• Output: [0,1]
  De output nos mostrara cuales son esos dos valores Usando este ejemplo 2+7 es 9. Seria el indice 0,1

Codigo inicial en C#

public class Solution {
    public int[] TwoSum(int[] nums, int target) {

    }
}

Vemos que tenemos TwoSum que contiene el arreglo y el int target con esto en cuenta podemos seguir para el primer step:

Primer paso:

Recorremos el arreglo usando un for. De esta mientras que i sea menor a nums.Length; le sumaras 1 a la i por cada iteracion.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {

        for(int i = 0; i<nums.Length; i++) {

        }
    }
}

Segundo Paso:

Como necesitamos dos indices que se sumen para verificar si es el numero que tiene target. Hacemos otro for para recorrer el proximo indice en el arreglo. Esto se logra sumandole +1 al segundo for.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {

        for(int i = 0; i<nums.Length; i++) {
          for(int j = i+1; j<nums.Length; j++){

          }

        }
    }
}

Tercer Paso:

Finalmente ya con ambos for listos, creamos el condicional que nos retornara los indices en caso de ser sumados y ser igual a target.
return new int[] {i,j}; esto nos guardara un nuevo arreglo tipo int con los dos indices.
En caso de no conseguir ninguno, fuera de todos los for: return nums; mostrara el arreglo.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {

        for(int i = 0; i<nums.Length; i++) {
            for(int j = i+1; j<nums.Length; j++){
                if(target == nums[i] + nums[j]) {
                    return new int[] {i,j};
                }
            }
        }
        return nums;
    }
}

Conclusion

Es un problema altamente conocido en el mundo de la programacion. Sirve para tener una buena base de cosas como iterar con los for para moverse entre los indices.