Перейти к содержанию

Two sum

Ссылка с заданием на литкоде

Описание

Для заданого массива целых чисел nums и целого числа target необходимо вернуть два индекса в nums. Сумма чисел по этим индексам должна образовывать число target.

Гарантируется, что при любых тестовых данных есть только одно решение, оба числа могут быть одинаковыми, но их индексы будут разными.

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

Пример 1:

Входные данные: nums = [2, 7, 11, 15], target = 9
Выходные данные: [0, 1]
Объяснение: Поскольку nums[0] + nums[7] == 9, мы вернули [0, 1]

Пример 2:

Входные данные: nums = [3, 2, 4], target = 6
Выходные данные: [1, 2]

Пример 3:

Входные данные: nums = [3, 3], target = 6
Выходные данные: [0, 1]

Идея решения

Решение в лоб для данного примера будет представлять проверку всех возможных комбинаций. Берём первое число в массиве и ищем, есть ли в массиве число равное разности target и текущему числу. В данном случае решение не будет эффективным, однако его можно взять за основу и ускорить используя хэш-таблицу.

Алгоритм решения

Можно решить это задание эффективно, всего за один проход. Нам необходимо вернуть индексы тех значений, которые в сумме дают target. Мы можем хранить вместо самого значения необходимую ему пару. Пример: Если мы встретили с индексом index = 0 число num = 7, а наш target = 10 то мы можем сохранить эту информацию в паре target - num: index и встретив число num = target - num в следующий раз нам необходимо будет вернуть два индекса, текущий индекс числа и сохранёный индекс его пары.

Таким образом наш алгоритм выглядит так: 1. создаём хэш-таблицу для хранения пар target - num: index 2. итерируем наш список чисел nums сохраняя идекс текущего числа и получая подходящее число(которое в сумме с текущим даёт target) 3. если мы уже встречали такое подходящее число, то возвращаем индекс текущего числа и сохранёный инедкс подходящего числа 4. добавляем пару подходящего числа и текущего индекса в хэш-таблицу

Сложность

  • По времени: \(O(N)\) n = len(nums)

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

Скорость поиска в хэш-таблицах O(1), так что поиск эллемента не замедляет алгоритм.

  • По памяти: \(O(N)\) n = len(nums)

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

Код решения:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        stack = {}

        for index, num in enumerate(nums):
            compliment_number = target - num
            if compliment_number in stack:
                return stack[compliment_number], index
            stack[num] = index

use std::collections::{HashSet, HashMap};

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut stack = HashMap::new();

        for (index, number) in nums.iter().enumerate() {
            let compliment = target - number;

            if let Some(&i) = stack.get(&compliment) {
                return vec![i as i32, index as i32];
            }
            stack.insert(*number, index);
        }
        unreachable!()
    }
}