Проблема с двумя суммами LeetCode объясняется простыми словами с использованием словаря

Проблема

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

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

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

Пример 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Пример 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Пример 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Давайте начнем

Как обычно, наша главная цель — решить задачу и в то же время добиться наилучшей временной сложности при минимальной пространственной сложности. Если вы новичок в решении проблем или пытаетесь решить проблемы со структурой данных, я предлагаю вам начать с подхода грубой силы, а затем попытаться оптимизировать свое решение до наилучшей временной/пространственной сложности.

Анализ

Прежде чем переходить к решению или псевдокоду, прочтите пару раз условие задачи и убедитесь, что хорошо его поняли.
Для начала мы можем проверить каждое число в массиве, сравнив его сумму со всеми другими числами. Это даст сложность O(\( n² \)) с простым подходом грубой силы.
Давайте посмотрим, как мы можем сделать это лучше. Предположим, что нам нужно найти два числа: A и B. Если A — текущий элемент в нашей итерации цикла. B — другое число в том же массиве.
A + B = цель. тогда В = цель — А.
Как насчет того, чтобы мы могли хранить/отслеживать (цель — A) в структуре данных, когда мы просматриваем каждое число в массиве? Мы будем хранить разницу в наборе только в том случае, если она еще не существует. Если он уже существует, то ответом являются текущий индекс и индекс сохраненного значения. Мы просто вернем его.
Словарь — лучший кандидат структуры данных для нашего решения на C#. В Java мы можем использовать Hashtable.

Разница между Hashtable и словарем в С#

Словарь — это общая коллекция, которая обычно используется для хранения пар ключ/значение. Словарь определен в пространстве имен System.Collection.Generics. Он динамичен по своей природе, что означает, что размер словаря растет по мере необходимости.

Hashtable — это набор пар ключ/значение, организованных на основе хэш-кода ключа. Это неуниверсальный тип коллекции, определенный в пространстве имен System.Collections.

Алгоритм | Псевдокод

Создайте словарь для хранения значения (цель — текущий элемент) в массиве.
Итерируйте каждый элемент в массиве и получите разницу с целью.
Если значение разницы уже существует в словаре, это наш ответ. Возвращает индексы текущего элемента и соответствующее значение разницы, хранящееся в словаре.
В противном случае сохраните значение разницы в словаре.
В конце сгенерируйте исключение «Решение не найдено», если в нашем словаре нет элемента разницы.

Приступаем к написанию решения.

Перебрать элементы в массиве. Если мы найдем элемент различия в словаре, который соответствует цели. Вот и все. Это наш ответ.

Заданный массив содержит два индекса, которые суммируют цель!

Решение (на С#)

class Solution {
       public int[] TwoSum(int[] nums, int target) {
       Dictionary<int,int> dict = new Dictionary<int,int>();
        for(int i=0;i<nums.Length;i++)
        {
            int diff = target-nums[i];
            if(dict.ContainsKey(diff))
                return new int[]{dict[diff],i};
            if(!dict.ContainsKey(nums[i]))
                dict.Add(nums[i],i);
        }
        throw new Exception("No solution found");
    }
    }

Сложность

Временная сложность => O(n) => Обходим массив один раз. Dictionary Add() Содержит операции O(1) раз.
Space Complexity =› O(n) =› Dictionary хранит не более n пар ключ-значение.

Вывод

Эта задача является очень хорошим примером использования структуры Hashtable/Dictionary Data для снижения сложности с O(\( n² \)) до O(n). Ознакомьтесь с дополнительными примерами в этой категории для дальнейшего изучения.

использованная литература

Проблема LeetCode в этой статье:

https://leetcode.com/problems/two-sum/

Спасибо, что прочитали этот пост!

Я надеюсь, что эта статья будет информативной и полезной в некотором роде. Если да, ставьте лайк и делитесь! Следите за мной в Твиттере | LinkedIn для связанного контента.

Приятного обучения!

Первоначально опубликовано на https://geetcloud.blogspot.com 6 сентября 2021 г.

Проблема с двумя суммами LeetCode объясняется простыми словами с использованием словаря