Привет, ребята, сегодня я расскажу об ОДНОЙ ИЗ САМЫХ ПРОСТЫХ ПРОБЛЕМ в LeetCode. Это задача двух сумм. Давайте начнем.

  1. Во-первых, мы должны посмотреть вопрос.

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

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

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

Прохладный. Они также дали нам 3 примера.

Пример 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]

Ограничения:

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

Дополнительные сведения. Можете ли вы придумать алгоритм со сложностью менее O(n2) time?

МЕТОД ХЭШМАПЫ:

class Solution {
public:
vector‹int› twoSum(vector‹int›& nums, int target) {
vector‹int›ans;
unordered_map‹int,int›m;

for(int i=0;i‹nums.size();i++)
{
int val = target -nums[i];
if(m.find(val)!=m.end())// если найден второй элемент
{
ans.push_back(m.find(val)-›second);
ans.push_back(i);
break;
}
m.insert(pair‹int, int›(числа[i],i));
}
вернуть ответ;
}
};