Вопрос: вам дан целочисленный массив и целевое число. Вам нужно найти два числа в массиве, которые в сумме дают заданное целевое число. Предположения - для каждого входа существует ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Пример: [1, 2, 3, 14], цель = 4

Ожидаемое решение: [0, 2] (ПРИМЕЧАНИЕ. [1,1] также дает вам сумму 4, но, согласно формулировке проблемы, это неприемлемое решение)

Первые мысли:

  1. Массив отсортирован? - ну, это не может быть установлено с помощью постановки задачи. Итак, допустим худшее - это несортированный массив.
  2. Могут ли в массиве быть повторяющиеся значения? - Может быть. Не упоминается, будет ли массив уникальным, поэтому предположим, что могут быть дубликаты.

Подход 1:

Учитывая тот факт, что входной массив не отсортирован, мои рефлексы сработали, чтобы отсортировать массив. Но после нескольких неудачных попыток выяснилось, что подходы, которые у меня были, не окупились достаточно большими первоначальными вложениями в сортировку массива. Поэтому мы возвращаемся и выбираем другой маршрут.

Этот подход требует операций быстрой выборки и не учитывает порядок, в котором вы предоставляете данные. Карты кажутся инстинктивным выбором для такого решения. Каждое число в массиве проверяется, является ли это возможным решением, проверяя, встречалось ли уже значение разницы (target-currentNumber) в массиве (проверяя, содержит ли его карта). В противном случае добавьте currentNumber к этой карте для будущих проверок.

//Approach 1.a
//Runtime: 3ms
//Memory usage: 39.3MB
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0;
            for(int num : nums){
            if(map.containsKey(target - num)){
                return new int[]{map.get(target - num), index};
            }
            map.put(num, index++);
        }
        return new int[]{};
    }
/******************************************************************/
//Approach 1.b
//Runtime: 2ms
//Memory usage: 38MB
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int index = 0; index<nums.length; index++){
            if(map.containsKey(target - nums[index])){
                return new int[]{map.get(target - nums[index]), index};
            }
/*Don't have to keep updating the HashMap if there are multiple values. A put() call can be expensive, so let's avoid it if we can*/
            if(!map.containsKey(nums[index])){
                map.put(nums[index], index);
            }
        }
        return new int[]{};
    }

Этот подход определенно быстрее, чем наивное решение сравнения каждого числа с остальными элементами в массиве. Но компромисс здесь - использование пространства. Конечно, существует гораздо больше подходов. Вероятно, мы рассмотрим их в следующих публикациях.

Больше постов ищите здесь.

Ура и Чао!