почему не получится, если сделать map.put перед проверкой решений при решении Leetcode Two Sum с использованием hashmap?

Question

Для классической задачи Leetcode TwoSum: для заданного массива целых чисел вернуть индексы двух чисел так, чтобы они складывались до определенной цели.

Можно предположить, что каждый вход будет иметь только одно решение, и вы не можете использовать один и тот же элемент дважды.

Пример:

Учитывая nums = [2, 7, 11, 15], target = 9, потому что nums [0] + nums [1] = 2 + 7 = 9, верните [0, 1].

пробный код ниже, он пройдет тестовые случаи, но не получится для отправки.

public class Solution {
    public int[] twoSum (int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            throw new IllegalArgumentException ("array given is null or 
length less than 1, no two sum solutions"); 
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < arr.length; i++) {
            map.put (arr[i], i);
            int component = target -arr[i]; 
            if (map.containsKey(component) && map.get(component) != i) {
                return new int[] {i, map.get(component)};
            }
        }   
        throw new IllegalArgumentException (" no two sum solution found 
"); 
    }
}

Хотя, если я простопереместите map.put после того, как проверка решения, как показано ниже, пройдет, не можете понять, почему?

public class Solution {
    public int[] twoSum (int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            throw new IllegalArgumentException ("array given is null or 
length less than 1, no two sum solutions"); 
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < arr.length; i++) {

            int component = target -arr[i]; 
            if (map.containsKey(component) && map.get(component) != i) {
                return new int[] {i, map.get(component)};
            }
            map.put (arr[i], i);
        }   
        throw new IllegalArgumentException (" no two sum solution found 
"); 
    }
}

Answer 1

Ваш первый фрагмент не удастся, если массив содержит дубликаты, а target - сумма двух равных элементов массива.

Предположим, что target == arr[i] + arr[j] для некоторых i и j, таких что i <<code>j и arr[i]==arr[j].В этом случае вы сначала положите map.put (arr[i], i), а затем перезапишите его map.put (arr[j], j).В результате map.containsKey(component) будет true, но map.get(component) != i будет false, и вам не удастся вернуть пару индексов i и j.

Следовательно, вам следуетдобавьте текущий элемент к Map только после проверки условия.

Например, следующий ввод не удастся в первом решении и преуспеет во втором:

twoSum(new int[] {4,5,7,5},10)

Answer 2

Рассмотрим тестовый пример [5,5,8] и цель 10; тогда контрольный пример не пройден, если вы поставите map map.put (arr[i], i); перед проверкой решения

для того же ключа вы переопределяете индексы на карте