Three Sum

En este blog, te enseñaré cómo resolver el ejercicio Three Sum de la plataforma LeetCode en Java, Python, PHP, C++ y JavaScript en español.

En esta guía, aprenderás a:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript

Este ejercicio se encuentra en la plataforma de LeetCode como "Three Sums".

                       

Problema

Dado un arreglo de enteros nums, encuentra todos los tres números consecutivos que sumen 0. 



Pasos para realizar el algoritmo:

1.- Se ordena el array de números. Esto se hace para que podamos recorrerlo de manera eficiente, y se crea una lista vacía para almacenar las respuestas.

2.- Se itera sobre el array de números, comenzando en el índice 0.

3.- Se verifica si el índice actual es mayor que 0 y si el número en el índice actual es igual al número en el índice anterior. Si es así, se continúa con el siguiente valor. Esto se hace para evitar agregar duplicados a la respuesta.

4.- Se inicializan dos variables, izquierda y derecha, que representan los índices de los dos números restantes que se usarán para calcular la suma.

5.- Se calcula la suma de los tres números.

6.1.- Si la suma es igual a 0, se agrega la lista de los tres números a la lista de respuestas.

6.1.1.- Se incrementa el índice izquierda y se decrementa el índice derecha para recorrer los siguientes números.

6.1.2.- Para evitar duplicados, se verifica si los números en los índices izquierda y derecha ya han sido considerados. Si es así, se continúa con los siguientes índices.

6.2.-  Si la suma es menor que 0, se incrementa el índice izquierda para buscar un número mayor.

6.3.- Si la suma es mayor que 0, se decrementa el índice derecha para buscar un número menor.

7.- Se devuelve la lista de respuestas.

Presentación

Código en Java

public class Solution {
 
    public List<List<Integer>> threeSum(int[] nums) {
        // paso#1
        Arrays.sort(nums);
        List<List<Integer>> response = new ArrayList<>();
 
        // paso#2
        for (int i = 0; i < nums.length - 2; i++) {
 
            // paso#3
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
 
            // paso#4
            int izquierda = i + 1;
            int derecha = nums.length - 1;
 
            while (izquierda < derecha) {
                // paso#5
                int sum = nums[i] + nums[izquierda] + nums[derecha];
 
                // paso#6.1
                if (sum == 0) {
                    response.add(Arrays.asList(nums[i], nums[izquierda], nums[derecha]));
 
                    // paso#6.1.1
                    izquierda++;
                    derecha--;
 
                    // paso#6.1.2
                    while (izquierda < derecha && nums[izquierda] == nums[izquierda - 1])
                        izquierda++;
                    while (izquierda < derecha && nums[derecha] == nums[derecha + 1])
                        derecha--;
                }
 
                // paso#6.2
                else if (sum < 0)
                    izquierda++;
                // paso#6.3
                else
                    derecha--;
 
            }
        }
        // paso#7
        return response;
    }
}

Código en php

class Solution {
 
    public function threeSum(array $nums): array {
        // paso#1
        sort($nums);
        $respuesta = [];
 
        // paso#2
        for ($i = 0; $i < count($nums) - 2; $i++) {
 
            // paso#3
            if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
                continue;
            }
 
            // paso#4
            $izquierda = $i + 1;
            $derecha = count($nums) - 1;
 
            while ($izquierda < $derecha) {
                // paso#5
                $suma = $nums[$i] + $nums[$izquierda] + $nums[$derecha];
 
                // paso#6.1
                if ($suma === 0) {
                    $respuesta[] = [$nums[$i], $nums[$izquierda], $nums[$derecha]];
 
                    // paso#6.1.1
                    $izquierda++;
                    $derecha--;
 
                    // paso#6.1.2
                    while ($izquierda < $derecha && $nums[$izquierda] === $nums[$izquierda - 1]) {
                        $izquierda++;
                    }
                    while ($izquierda < $derecha && $nums[$derecha] === $nums[$derecha + 1]) {
                        $derecha--;
                    }
                }
 
                // paso#6.2
                elseif ($suma < 0) {
                    $izquierda++;
                }
 
                // paso#6.3
                else {
                    $derecha--;
                }
            }
        }
 
        // paso#7
        return $respuesta;
    }
}
 

Código en Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # paso#1
        nums.sort()
        respuesta = []
 
        # paso#2
        for i in range(len(nums) - 2):
 
            # paso#3
            if i > 0 and nums[i] == nums[i - 1]:
                continue
 
            # paso#4
            izquierda = i + 1
            derecha = len(nums) - 1
 
            while izquierda < derecha:
                # paso#5
                suma = nums[i] + nums[izquierda] + nums[derecha]
 
                # paso#6.1
                if suma == 0:
                    respuesta.append([nums[i], nums[izquierda], nums[derecha]])
 
                    # paso#6.1.1
                    izquierda += 1
                    derecha -= 1
 
                    # paso#6.1.2
                    while izquierda < derecha and nums[izquierda] == nums[izquierda - 1]:
                        izquierda += 1
                    while izquierda < derecha and nums[derecha] == nums[derecha + 1]:
                        derecha -= 1
 
                # paso#6.2
                elif suma < 0:
                    izquierda += 1
 
                # paso#6.3
                else:
                    derecha -= 1
 
        # paso#7
        return respuesta

Código en C++

#include <algorithm>
#include <vector>
 
class Solution {
public:
  std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    // paso#1
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> response;
 
    // paso#2
    for (int i = 0; i < nums.size() - 2; i++) {
 
      // paso#3
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
 
      // paso#4
      int izquierda = i + 1;
      int derecha = nums.size() - 1;
 
      while (izquierda < derecha) {
        // paso#5
        int suma = nums[i] + nums[izquierda] + nums[derecha];
 
        // paso#6.1
        if (suma == 0) {
          response.push_back({nums[i], nums[izquierda], nums[derecha]});
 
          // paso#6.1.1
          izquierda++;
          derecha--;
 
          // paso#6.1.2
          while (izquierda < derecha && nums[izquierda] == nums[izquierda - 1]) {
            izquierda++;
          }
          while (izquierda < derecha && nums[derecha] == nums[derecha + 1]) {
            derecha--;
          }
        }
 
        // paso#6.2
        else if (suma < 0) {
          izquierda++;
        }
 
        // paso#6.3
        else {
          derecha--;
        }
      }
    }
 
    // paso#7
    return response;
  }
};

Código en JavaScript

var threeSum = function(nums) {
// paso#1
  nums.sort((a, b) => a - b);
  const response = [];
 
  // paso#2
  for (let i = 0; i < nums.length - 2; i++) {
    // paso#3
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
 
    // paso#4
    let izquierda = i + 1;
    let derecha = nums.length - 1;
 
    while (izquierda < derecha) {
      // paso#5
      const suma = nums[i] + nums[izquierda] + nums[derecha];
 
      // paso#6.1
      if (suma === 0) {
        response.push([nums[i], nums[izquierda], nums[derecha]]);
 
        // paso#6.1.1
        izquierda++;
        derecha--;
 
        // paso#6.1.2
        while (izquierda < derecha && nums[izquierda] === nums[izquierda - 1]) {
          izquierda++;
        }
        while (izquierda < derecha && nums[derecha] === nums[derecha + 1]) {
          derecha--;
        }
      }
 
      // paso#6.2
      else if (suma < 0) {
        izquierda++;
      }
 
      // paso#6.3
      else {
        derecha--;
      }
    }
  }
 
  // paso#7
  return response;
};

        
    
Conclusión
En este blog, hemos visto cómo realizar el ejercicio Three Sum en Java, Python, PHP, C++ y JavaScript.

Hemos visto ejemplos de código en cada lenguaje de programación.