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; } |