Un problème Java résolu à l'aide d'un algorithme (problème de hashmap)

Question

La première question de leetcode, cette méthode peut atteindre une solution de complexité O(n)

La question nécessite un int[], tel que nums = [2, 7, 11, 15] et une cible = 9.
S'il y a deux nombres dont la somme est la valeur cible, par exemple nums[0] + nums[1] = 2 + 7 = 9
retournez [0, 1].

Lorsque j'utilise la solution suivante, j'ai un petit doute, c'est-à-dire qu'une nouvelle hashmap est créée, mais aucune valeur ne lui est attribuée. Comment répondez-vous aux exigences de la question dans ce cas ?

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

Answer 1

Map.put() dans la boucle for n'est-il pas une affectation ? ? ?

Answer 2

La question nécessite que la somme de deux nombres soit la valeur cible et une valeur donnée, alors vous devez parcourir au moins deux nombres
(1) Si vous initialisez d'abord, cela prendra le temps de l'algorithme O(n) ; trouvez le premier Lorsque la valeur est correcte, le temps de l'algorithme est O(k), 0<k<n. Le temps total est O(n+k), pour déterminer s'il s'agit de vous-même, par exemple (10 = 5 + 5). ).
　La réalisation de cette situation est :

　　1) Initialisez d'abord la carte,
　 2) Parcourez le premier chiffre 2, cible - 2 = 9 - 2 = 7
　 3) Jugez que 7 est également dans la carte et renvoyez le résultat correct.
Remarque : Traversez jusqu'au premier numéro correct

　
(2) S'il n'est pas initialisé, il passera au deuxième nombre correct avant de s'arrêter. Le temps de l'algorithme est O(k)(1<k<=n).
La réalisation de cette situation est :

　1)遍历第一个数2, target - 2 = 9 - 2 = 7
　2)判断7是否在map，发现不在，把2加入map,继续遍历
　3)直到遍历到７, target - 7 = 9 - 7 = 2
　4)判断2在map,返回正确结果
　注意，要遍历到第二个正确数.

Answer 3

Non Key 的情况下，HashMap.containsKey(Key) 返回的是 false 不包括 Key.

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

Il n'y aura pas d'erreur de pointeur nul comme vous le pensez.