Este artículo explora la solución de varios problemas de algoritmos, enfocándose en el uso de tablas hash (unordered_map en C++) y la técnica de dos punteros, especialmente después de ordenar los datos.
454. Suma de Cuatro Elementos (Conteo de Pares)
El problema consiste en encontrar el número de combinaciones de cuatro listas de enteros (nums1, nums2, nums3, nums4) tales que la suma de un elemento de cada lista sea cero. Una estrategia eficiente es calcular todas las sumas posibles de pares de las dos primeras listas y almacenarlas en una tabla hash, donde la clave es la suma y el valor es su frecuencia. Luego, para cada par de la tercera y cuarta lista, buscamos en la tabla hash si existe una suma que sea el negativo de la suma actual (0 - (c + d)). Si se encuentra, sumamos su frecuencia al contador total.
#include <vector>
#include <unordered_map>
class Solution {
public:
int fourSumCount(std::vector<int>& nums1, std::vector<int>& nums2, std::vector<int>& nums3, std::vector<int>& nums4) {
std::unordered_map<int, int> sums_map;
int count = 0;
// Calcular y almacenar sumas de nums1 y nums2
for (int val1 : nums1) {
for (int val2 : nums2) {
sums_map[val1 + val2]++;
}
}
// Buscar complementos en nums3 y nums4
for (int val3 : nums3) {
for (int val4 : nums4) {
int target_sum = -(val3 + val4);
if (sums_map.count(target_sum)) {
count += sums_map[target_sum];
}
}
}
return count;
}
};
383. Construir Cadena desde el Magnífico
Este problema requiere determinar si se puede construir una cadena ransomNote utilizando los caracteres de otra cadena magazine. Una forma simple y eficiente es usar un arreglo de tamaño 26 para contar la frecuencia de cada letra del alfabeto en la cadena magazine. Luego, iteramos sobre la cadena ransomNote, decrementando la cuanta de cada carácter. Si en algún momento la cuenta de un carácter se vuelve negativa, significa que no hay suficientes caracteres disponibles en magazine, y devolvemos false. Si completamos la iteración sin que ninguna cuenta se vuelva negativa, devolvemos true.
#include <string>
#include <vector>
class Solution {
public:
bool canConstruct(std::string ransomNote, std::string magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
int char_counts[26] = {0}; // Inicializar todas las cuentas a 0
// Contar frecuencias de caracteres en magazine
for (char c : magazine) {
char_counts[c - 'a']++;
}
// Verificar si ransomNote puede ser construida
for (char c : ransomNote) {
char_counts[c - 'a']--;
if (char_counts[c - 'a'] < 0) {
return false;
}
}
return true;
}
};
15. Suma de Tres Elementos
El objetivo es encontrar todos los tripletos únicos en un arreglo nums cuya suma sea cero. La estrategia implica primero ordenar el arreglo. Luego, iteramos a través del arreglo con un índice i. Para cada nums[i], usamos dos punteros, left (comenzando en i + 1) y right (comenzando al final del arreglo), para encontrar los dos elementos restantes que sumen -nums[i]. Es crucial manejar los duplicados para asegurar que los tripletos resultantes sean únicos. Si nums[i] es positivo, podemos detenernos ya que el arreglo está ordenado y todas las sumas subsiguientes serán positivas. También, si nums[i] es el mismo que el elemento anterior, lo saltamos para evitar tripletos duplicados.
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
// Si el elemento actual es positivo, no se pueden formar sumas de cero
if (nums[i] > 0) {
break;
}
// Saltar duplicados para el primer elemento
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
int current_sum = nums[i] + nums[left] + nums[right];
if (current_sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
// Saltar duplicados para el segundo y tercer elemento
while (right > left && nums[right] == nums[right - 1]) {
right--;
}
while (right > left && nums[left] == nums[left + 1]) {
left++;
}
right--;
left++;
} else if (current_sum > 0) {
right--;
} else {
left++;
}
}
}
return result;
}
};
18. Suma de Cuatro Elementos
Este problema es una extensión del anterior, buscando cuádrupletos únicos cuya suma sea igual a un target dado. Similar a threeSum, primero ordenamos el arreglo. Luego, anidamos dos bucles exteriores para los dos primeros elementos (nums[k] y nums[i]) y usamos la técnica de dos punteros (left y right) para encontrar los dos elementos restantes. Se deben implementar optimizaciones y manejos de duplicados para los cuatro elementos. Las condiciones de parada y los saltos de duplicados son similares a los de threeSum, pero aplicados a los dos bucles exteriores y a los punteros internos. Se utiliza long long para evitar desbordamientos al sumar cuatro enteros.
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
std::vector<std::vector<int>> result;
std::sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 3; ++i) {
// Saltar duplicados para el primer elemento
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Optimización: si la suma mínima ya es mayor que el target
if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
// Optimización: si la suma máxima con este primer elemento es menor que el target
if ((long long)nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) {
continue;
}
for (int j = i + 1; j < n - 2; ++j) {
// Saltar duplicados para el segundo elemento
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// Optimización: si la suma mínima con los dos primeros ya es mayor que el target
if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
// Optimización: si la suma máxima con los dos primeros es menor que el target
if ((long long)nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) {
continue;
}
int left = j + 1;
int right = n - 1;
while (right > left) {
long long current_sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
if (current_sum == target) {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
// Saltar duplicados para el tercer y cuarto elemento
while (right > left && nums[right] == nums[right - 1]) {
right--;
}
while (right > left && nums[left] == nums[left + 1]) {
left++;
}
right--;
left++;
} else if (current_sum > target) {
right--;
} else {
left++;
}
}
}
}
return result;
}
};