Two Sum. Algorithms on Golang from LeetCode

Задача

Функция получает на вход целочисленный срез (nums) и результат сложения (target). Необходимо вернуть индексы двух чисел, сумма которых равна target.

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

Пример

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

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

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

Тесты

func TestTwoSum(t *testing.T) {
	cases := []struct {
		nums   []int
		target int
		want   []int
	}{
		{[]int{2, 7, 11, 15}, 9, []int{0, 1}},
		{[]int{3, 2, 4}, 6, []int{1, 2}},
		{[]int{3, 3}, 6, []int{0, 1}},
	}
	for _, s := range cases {
		got := twoSum(s.nums, s.target)
		if !reflect.DeepEqual(got, s.want) {
			t.Errorf("twoSum = %v; want %v", got, s.want)
		}
	}
}

Approach 1: Brute Force

Brute force подход самый простой. Проходим в цикле по всем элементам x и ищем, существует ли другое значение равное target - x.

func twoSum(nums []int, target int) []int {
    for i := range nums {
        for j := i + 1; j < len(nums); j++ {
            if nums[j] == target - nums[i] {
                return []int{i, j}
            }
        }
    }
    return nil
}

Временная сложность: O(n^2).

Для каждого элемента мы пытаемся найти его слагаемое, перебирая остальную часть среза, что занимает O(n) времени. Следовательно, временная сложность будет O(n^2).

Approach 2: Two-pass Hash Table

Чтобы улучшить нашу сложность во время выполнения, нам нужен более эффективный способ проверить, существует ли слагаемое в срезе. Если слагаемое существует, нам нужно найти его индекс. Какой лучший способ поддерживать отображение каждого элемента среза в его индекс? Хеш-таблица.

Мы сокращаем время поиска с O(n) до O(1). Хеш-таблица создана именно для этой цели, она поддерживает быстрый поиск почти за постоянное время. Я говорю “почти”, потому что в случае коллизии получение значения из хеш-таблицы может деградировать до O(n).

Простая реализация использует две итерации. На первой итерации мы добавляем значение каждого элемента и его индекс в хеш-таблицу. Затем, на второй итерации мы проверяем, существует ли в таблице слагаемое для target - nums[i]. Важно, что слагаемое не должно быть равно nums[i].

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := range nums {
        m[nums[i]] = i
    }
    for i := range nums {
        complement := target - nums[i]
        if v, ok := m[complement]; ok {
            if m[complement] != i {
                return []int{i, v}
            }
        }
    }
    return nil
}

Временная сложность: O(n).

Обходим срез, содержащий n элементов, ровно дважды. Поскольку хеш-таблица сокращает время поиска до O(1), то сложность становится O(n).

Approach 3: One-pass Hash Table

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

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i := range nums {
        complement := target - nums[i]
        if v, ok := m[complement]; ok {
                return []int{i, v}
        }
        m[nums[i]] = i
    }
    return nil
}

Временная сложность: O(n)