Вопрос: вам дан целочисленный массив и целевое число. Вам нужно найти два числа в массиве, которые в сумме дают заданное целевое число. Предположения - для каждого входа существует ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Пример: [1, 2, 3, 14], цель = 4
Ожидаемое решение: [0, 2] (ПРИМЕЧАНИЕ. [1,1] также дает вам сумму 4, но, согласно формулировке проблемы, это неприемлемое решение)
Первые мысли:
- Массив отсортирован? - ну, это не может быть установлено с помощью постановки задачи. Итак, допустим худшее - это несортированный массив.
- Могут ли в массиве быть повторяющиеся значения? - Может быть. Не упоминается, будет ли массив уникальным, поэтому предположим, что могут быть дубликаты.
Подход 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[]{}; }
Этот подход определенно быстрее, чем наивное решение сравнения каждого числа с остальными элементами в массиве. Но компромисс здесь - использование пространства. Конечно, существует гораздо больше подходов. Вероятно, мы рассмотрим их в следующих публикациях.
Больше постов ищите здесь.
Ура и Чао!