План курса / Все задачи / Алгоритмы и структуры данных
Сумма двух чисел
легко
# решено
Дан массив целых чисел nums и число target. Нужно вернуть индексы двух чисел из массива nums, которые дают в сумме target.
ВАЖНО: гарантированно есть только один ответ, при этом индексы нужно вернуть в возрастающем порядке.
Пример 1:
Ввод: nums = [1,4,3,-6,2,5], target = -1
Вывод: [3,5]
Объяснение: -6 + 5 = -1. "-6" имеет индекс 3, а "5" индекс 5.
Пример 2:
Ввод: nums = [4,6,4], target = 8
Вывод: [0,2]
Объяснение: дублировать число нельзя, поэтому ответы [0,0] и [2,2] не подходят.
Ограничения:
2 <= len(nums)
public class Solution
{
public static List<int> TwoSum(List<int> nums, int target)
{
// ключ - число, значение - на какой позиции встретили число
Dictionary<int, int> usedNums = new Dictionary<int, int>();
for (int idx = 0; idx < nums.Count; ++idx)
{
int secondNum = nums[idx];
// firstNum - число, которое должны были встретить раньше
// чтобы текущее число (secondNum) + firstNum дало в сумме target
int firstNum = target - secondNum;
// если firstNum уже встречали в массиве, значит мы нашли
// пару чисел, дающие в сумме target и возвращаем их индексы
if (usedNums.ContainsKey(firstNum))
{
return new List<int> { usedNums[firstNum], idx };
}
usedNums[secondNum] = idx;
}
return new List<int>();
}
}
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> twoSum(const vector<int>& nums, int target) {
// ключ - число, значение - на какой позиции встретили число
unordered_map<int, int> usedNums;
for (int idx = 0; idx < nums.size(); ++idx) {
int secondNum = nums[idx];
// firstNum - число, которое должны были встретить раньше
// чтобы текущее число (secondNum) + firstNum дало в сумме target
int firstNum = target - secondNum;
// если firstNum уже встречали в массиве, значит мы нашли
// пару чисел, дающие в сумме target и возвращаем их индексы
if (usedNums.find(firstNum) != usedNums.end()) {
return {usedNums[firstNum], idx};
}
usedNums[secondNum] = idx;
}
return {};
}
package main
func twoSum(nums []int, target int) []int {
// ключ - число, значение - на какой позиции встретили число
usedNums := make(map[int]int)
for idx, secondNum := range nums {
// firstNum - число, которое должны были встретить раньше
// чтобы текущее число (secondNum) + firstNum дало в сумме target
firstNum := target - secondNum
// если firstNum уже встречали в массиве, значит мы нашли
// пару чисел, дающие в сумме target и возвращаем их индексы
if firstNumIdx, found := usedNums[firstNum]; found {
return []int{firstNumIdx, idx}
}
usedNums[secondNum] = idx
}
return []int{}
}
import java.util.*;
public class Solution {
public List<Integer> twoSum(List<Integer> nums, int target) {
// ключ - число, значение - на какой позиции встретили число
Map<Integer, Integer> usedNums = new HashMap<>();
for (int idx = 0; idx < nums.size(); idx++) {
int secondNum = nums.get(idx);
// firstNum - число, которое должны были встретить раньше
// чтобы текущее число (secondNum) + firstNum дало в сумме target
int firstNum = target - secondNum;
// если firstNum уже встречали в массиве, значит мы нашли
// пару чисел, дающие в сумме target и возвращаем их индексы
if (usedNums.containsKey(firstNum)) {
List<Integer> result = new ArrayList<>();
result.add(usedNums.get(firstNum));
result.add(idx);
return result;
}
usedNums.put(secondNum, idx);
}
return List.of();
}
}
from typing import *
def two_sum(nums: List[int], target: int) -> List[int]:
# ключ - число, значение - на какой позиции встретили число
used_nums = {}
for idx, second_num in enumerate(nums):
# first_num - число, которое должны были встретить раньше
# чтобы текущее число (second_num) + first_num дало в сумме target
first_num = target - second_num
# если first_num уже встречали в массиве, значит мы нашли
# пару чисел, дающие в сумме target и возвращаем их индексы
if first_num in used_nums:
return [used_nums[first_num], idx]
used_nums[second_num] = idx
return []
export function twoSum(nums, target) {
// ключ - число, значение - на какой позиции встретили число
const usedNums = new Map();
for (let i = 0; i < nums.length; i++) {
const secondNum = nums[i];
// firstNum - число, которое должны были встретить раньше
// чтобы текущее число (second_num) + first_num дало в сумме target
const firstNum = target - secondNum;
// если first_num уже встречали в массиве, значит мы нашли
// пару чисел, дающие в сумме target и возвращаем их индексы
if (usedNums.has(firstNum)) {
return [usedNums.get(firstNum), i];
}
usedNums.set(secondNum, i);
}
return [];
}