Решение задачи 1 “Two Sum” с LeetCode.

Условие задачи

Дан массив целых чисел, небходимо вернуть индексы двух элементов, сумма элементов которых равна числу target.

Замечание: Решение есть всегда и всегда одно. Один и тот же элемент нельзя использовать дважды

пример

1
2
3

Input: [2, 7, 11, 15] , 9
Output: [0, 1]
Пояснение: Сумма `nums[0]` и `nums[1]` равна заданному числу

Решение

Brute force

Идея алгоритма:

Идти по массиву. Выбрать элемент. А затем пробовать складывать его со всему последующими. Если сумма будет равна заданному числу - вернуть индексы элементов.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func twoSum(nums []int, target int) []int {
    for idx := 0;idx<len(nums)-1;idx++ {
        for jdx:=idx+1;jdx<len(nums);jdx++{
            if nums[idx]+nums[jdx]==target {
                return []int{idx,jdx}
            }
        }
    }
    return []int{}
}

Запоминать числа

Идея алгоритма:

Завести коллекцию элемент<->индекс элемента.

Идти по массиву:

• посчитать разницу target и текущего элемента
• проверить есть ли в коллеции элемент с ключом разницы
  • если есть - вернуть ключ текущего и значение из коллекции
  • если отсутствует - добавить в коллекцию элемент

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func twoSum(nums []int, target int) []int {
    q := make(map[int]int,len(nums))
    for idx:=range nums {
        add := target - nums[idx]
        if _, ok := q[add]; ok {
            return []int{idx, q[add]}
        }
        q[nums[idx]] = idx
    }
    
    return []int{}
}