Разбор задачи 1 Two Sum LeetCode.com

Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел так, чтобы они составляли в суммеtarget .

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

Вы можете вернуть ответ в любом порядке.

Ограничения:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Существует только один правильный ответ.

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

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

Решение Two Sum LeetCode пример кода на Python

class Solution:    
	# метод twoSum принимает на вход список nums и целевое значение target
    # и возвращает список из двух индексов чисел в nums, сумма которых равна target
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # словарь для хранения уже просмотренных чисел
        seen = {} 
		# проходимся по всем числам в списке nums с индексами
        for i, num in enumerate(nums): 
			# вычисляем "комплемент" - значение, которое должно быть в списке, чтобы получить target
            complement = target - num 
			# если комплемент уже был просмотрен, то нашли нужные индексы чисел
            if complement in seen: 
                return [seen[complement], i]
				# сохраняем текущее число и его индекс в словарь seen
            seen[num] = i 
		# если не найдено нужных индексов, возвращаем None
        return None 

Решение Two Sum LeetCode пример кода на Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // создание хэш-таблицы для хранения чисел и их индексов
        Map<Integer, Integer> map = new HashMap<>();
        // перебор массива чисел
        for (int i = 0; i < nums.length; i++) {
            // нахождение разности между целевым числом и текущим числом
            int complement = target - nums[i];
            // если такая разность уже есть в хэш-таблице, значит мы нашли пару чисел
            if (map.containsKey(complement)) {
                // возвращаем индексы двух чисел
                return new int[] { map.get(complement), i };
            }
            // добавляем текущее число и его индекс в хэш-таблицу
            map.put(nums[i], i);
        }
        // если не нашли пару чисел, выбрасываем исключение
        throw new IllegalArgumentException("No two sum solution");
    }
}

Решение Two Sum LeetCode пример кода на C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		// создание unordered_map для хранения чисел и их индексов
        unordered_map<int, int> mp;    
        for(int i = 0; i < nums.size(); i++) {
			// находим число-дополнение
            int complement = target - nums[i];  
			// если находим дополнение в unordered_map			
            if(mp.find(complement) != mp.end()) { 
				// возвращаем его индекс и текущий индекс
                return { mp[complement], i };   
            }
			// добавляем текущее число и его индекс в unordered_map
            mp[nums[i]] = i;   
        }
		// если нет решения, выбрасываем исключение
        throw invalid_argument("No two sum solution");   
    }
};

Решение Two Sum LeetCode пример кода на JavaScript

/**
 * Функция twoSum принимает на вход массив чисел nums и целевое число target.
 * Она возвращает массив с двумя индексами элементов, сумма которых равна целевому числу.
 * @param {number[]} nums - массив чисел
 * @param {number} target - целевое число
 * @returns {number[]} - массив с двумя индексами элементов
 * @throws {Error} - если решение не найдено
 */
const twoSum = function(nums, target) {
    // Создаем хэш-таблицу для хранения элементов и их индексов
    const map = new Map();
    // Итерируемся по массиву nums
    for (let i = 0; i < nums.length; i++) {
        // Вычисляем разность целевого числа и текущего элемента
        const complement = target - nums[i];
        // Если элемент-дополнительное слагаемое уже находится в хэш-таблице,
        // значит, мы нашли пару, сумма которой равна целевому числу
        if (map.has(complement)) {
            // Возвращаем массив с индексами элементов
            return [map.get(complement), i];
        }
        // Иначе, добавляем текущий элемент и его индекс в хэш-таблицу
        map.set(nums[i], i);
    }
    // Если не было найдено пары элементов, сумма которых равна целевому числу,
    // выбрасываем исключение
    throw new Error('No two sum solution');
};

Решение Two Sum LeetCode пример кода на c#

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> map = new Dictionary<int, int>(); // создание словаря
        for (int i = 0; i < nums.Length; i++) { // цикл по массиву
            int complement = target - nums[i]; // вычисление разности между целевым значением и текущим элементом массива
            if (map.ContainsKey(complement)) { // проверка наличия элемента-дополнения в словаре
                return new int[] { map[complement], i }; // возвращение пары индексов, если элемент-дополнение найден
            }
            map[nums[i]] = i; // добавление текущего элемента в словарь
        }
        throw new ArgumentException("No two sum solution"); // выброс исключения, если решение не найдено
    }
}