LeetCode предоставляет разнообразные задачи по программированию, в том числе и алгоритмические. Одной из таких задач является "Two Sum" - на первый взгляд, простая, но открывающая возможность глубже погрузиться в алгоритмы и структуры данных.
Описание задачи:
Дан массив целых чисел nums и целевое число target. Требуется найти два числа в массиве, сумма которых равна target, и вернуть их индексы. Предполагается, что ровно одно решение существует, и один и тот же элемент массива не может использоваться дважды.
Алгоритмическое решение:
- Подготовка: Создать словарь (Map) для хранения чисел из массива и их индексов.
- Пошаговый проход по массиву: Пройти по элементам массива.
Для каждого элемента num[i] проверить, есть ли число target - num[i] в словаре. - Поиск ответа: Если число target - num[i] уже присутствует в словаре, то мы нашли пару. Вернуть индексы текущего числа i и индекс числа target - num[i] value из map. Если нет, то добавить num[i] - key и i - value в словарь.
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i]))
return new int[]{map.get(target - nums[i]), i};
else map.put(nums[i], i);
}
return new int[0];
}
Примеры на которых можно проверить:
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Объяснение решения:
В этой реализации мы используем Map (словарь) для хранения чисел из массива и их индексов. Проходим по массиву, и для каждого числа проверяем, есть ли его комплемент (число, которое дает нужную сумму) в словаре. Если да, то мы нашли пару, и возвращаем индексы.
Это решение также работает за линейное время O(n), где n - количество элементов в массиве, что делает его эффективным методом решения подобных задач на практике.
Листинг:
import java.util.Arrays;
import java.util.HashMap;
public class TwoSum {
/*
Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
*/
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i]))
return new int[]{map.get(target - nums[i]), i};
else map.put(nums[i], i);
}
return new int[0];
}
/*
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
*/
public static void main(String[] args) {
TwoSum twoSum = new TwoSum();
Arrays.stream(twoSum.twoSum(new int[]{2,7,11,15},9)).forEach(System.out::println);
}
}
Заключение
Решение задачи Two Sum на LeetCode предоставляет отличную возможность углубиться в алгоритмическое мышление и применить базовые структуры данных.
Ключевыми моментами алгоритма являются использование словаря для хранения чисел и их индексов, а также пошаговый проход по массиву. Это позволяет нам эффективно находить пары чисел, сумма которых равна целевому значению.
Интересно отметить, что алгоритм работает за линейное время, что делает его привлекательным в контексте оптимизации производительности программ. Решение задачи Two Sum является лишь одним из множества примеров, демонстрирующих важность умения применять алгоритмы для решения реальных задач программирования. Мы надеемся, что данная статья послужит полезным ресурсом для тех, кто стремится углубить свои знания в области алгоритмов и структур данных.