Categorías
Algorithms

LeetCode – 3Sum

Problema:

Dada una matriz S de n enteros, ¿hay elementos a, b, c en S tales que a + b + c = 0? Encuentre todos los tripletes únicos en la matriz que da la suma de cero.

Nota:
Los elementos de un triplete (a, b, c) deben estar en orden no descendente. (es decir, a ≤ b ≤ c)
El conjunto de soluciones no debe contener tripletes duplicados.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solución Java

Este problema se puede resolver utilizando dos punteros. La complejidad del tiempo es O (n ^ 2).

Para evitar la duplicación, podemos aprovechar las matrices ordenadas, es decir, mover punteros en> 1 para usar el mismo elemento solo una vez.

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
 
    ArrayList<List<Integer>> result = new ArrayList<>();
 
    for (int i = 0; i < nums.length; i++) {
        int j = i + 1;
        int k = nums.length - 1;
 
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
 
        while (j < k) {
            if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                k--;
                continue;
            }
 
            if (nums[i] + nums[j] + nums[k] > 0) {
                k--;
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else {
                ArrayList<Integer> l = new ArrayList<>();
                l.add(nums[i]);
                l.add(nums[j]);
                l.add(nums[k]);
                result.add(l);
                j++;
                k--;
            }
        }
    }
 
    return result;
}

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *