Java - Leetcode Two Sum Hashmap Solution

Question

Je suis nouveau en Java et je viens de commencer à faire Leetcode - Two Sum. J'ai découvert qu'à part la solution par force brute, la solution la plus courante est l'utilisation de Hashmap. Mais je n'y arrive toujours pas. Par exemple, ceci fonctionne dans ma logique :

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
    int[] res = new int[2];
    for (int i = 0; i < nums.length; ++i) {
        m.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; ++i) {
        int t = target - nums[i];
        if (m.containsKey(t) && m.get(t) != i) {
            res[0] = i;
            res[1] = m.get(t);
            break;
        }
    }
    return res;
}

La première boucle for place les nombres dans Hashmap, et utilise la deuxième boucle for pour vérifier si nous pouvons trouver le nombre qui est égal à target number - nums[i] . Cependant, j'ai vu beaucoup de solutions acceptées qui combinaient les deux boucles for, comme dans cet exemple :

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

Dans ma logique, la deuxième solution consiste à exécuter la boucle for comme suit :

//[2,7,11,15]
when i=0, m.put(nums[0],2)
when i=1, m.put(nums[1],7)
when i=2, m.put(nums[2],11)
when i=3, m.put(nums[3],15)

Et parce que i < nums.length Ainsi, lorsque i=4, le code passe à return res . La boucle for ne sera pas réexécutée. Mais pour autant que je sache, j'ai vu des gens dire que la deuxième solution itère à travers le tableau, et stocke l'index et la valeur dans Hashmap, puis itère à nouveau. Dans mon imagination, il n'y a qu'une seule boucle for, comment peuvent-ils utiliser la seule boucle for pour itérer à nouveau ?

Answer 1

Il n'y aura pas de deuxième itération. Lors d'une itération, la boucle s'interrompra si une paire est trouvée.

considérer ce qui suit :

//[2,7,11,15] and target = 13
when i=0, m.put(mums[0],2)
when i=1, m.put(mums[1],7)
when i=2, m.contains(13 - mums[2]) == true // since 13 - 11 = 2 is present at index 0
res[0] = 2
res[1] = 0
break;

et donc, ..... vous avez raison. il n'y a qu'une seule itération.

Answer 2

Du point de vue des performances, il est préférable de n'itérer qu'une seule fois dans la boucle for et de sortir de la boucle lorsque la première paire correspondante est trouvée. Cette méthode est O(n) dans le pire des cas.

    public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        int rem = target - num;
        if (map.containsKey(rem)) {
            return new int[] { num, rem };
        }
        map.put(num, num);
    } // for
    return null;
}