Java - решение Leashcode Two Sum Hashmap

Question

Я новичок в Java, и я только начал делать Leetcode - Two Sum. Я обнаружил, что кроме решения «грубой силы», распространенным решением является использование Hashmap. Но я все еще не могу получить это. Например, это работает в моей логике:

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;
}

Первый цикл for помещает числа в Hashmap, а второй цикл for проверяет, можем ли мы найти число, равное target number - nums[i]. Тем не менее, я видел множество принятых решений, объединивших два цикла for, например, в следующем примере:

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;
}

По моей логике, второе решение запускает цикл for следующим образом:

//[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)

И поскольку i < nums.length, поэтому, когда я = 4, код будет переходить к return res. Он больше не будет запускать цикл for. Но насколько я знаю, я видел, как люди говорили, что второе решение будет проходить через массив, сохранять индекс и значение в Hashmap, а затем повторять снова. В моем воображении есть только один цикл for, как они могут использовать только один цикл for для повторения?

Answer 1

Нет необходимости в двух циклах for, и это можно сделать в одиночном цикле for, опубликованном вами. С точки зрения производительности лучше повторять только один раз в цикле for и прерывать цикл, когда первый соответствующая пара найдена. Это O (n) в худшем случае.

    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;
}

Answer 2

2-й итерации не будет.В одной итерации сам цикл прервется, если будет найдена пара.

рассмотрим это:

//[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;

и, следовательно, ..... вы правы.есть только одна итерация.