LeetCode – Dos sumas (Java)

Dada una matriz de números enteros, encuentre dos números que sumen un número objetivo específico.

La función twoSum debe devolver índices de los dos números de manera que se sumen al objetivo, donde index1 debe ser menor que index2. Tenga en cuenta que sus respuestas devueltas (tanto index1 como index2) no están basadas en cero.

Por ejemplo:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=0, index2=1

Solución Java

La solución óptima para resolver este problema es utilizar un HashMap. Para cada elemento de la matriz, (target-nums[i]) y el índice se almacenan en HashMap.

public int[] twoSum(int[] nums, int target) {
    if(nums==null || nums.length<2)
        return new int[]{0,0};
 
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0; i<nums.length; i++){
        if(map.containsKey(nums[i])){
            return new int[]{map.get(nums[i]), i};
        }else{
            map.put(target-nums[i], i);
        }
    }
 
    return new int[]{0,0};
}

La complejidad del tiempo es O (n).