Алгоритмы - Массивы

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

Алгоритм решения

  1. Инициализируем переменную maxLength для хранения максимальной длины.
  2. Проходим по массиву, начиная с первого элемента до предпоследнего.
  3. Для каждого элемента:
    • Устанавливаем левый указатель (left) на текущий элемент.
    • Устанавливаем правый указатель (right) на следующий элемент.
    • Двигаем правый указатель вправо, пока встречаются элементы, равные текущему.
    • Вычисляем длину найденной подпоследовательности (right - left).
    • Обновляем maxLength, если найденная длина больше.
    • Перемещаем индекс i на конец найденной подпоследовательности минус 1.
  4. Возвращаем maxLength.

Временная сложность: O(n), где n - длина массива. Несмотря на вложенный цикл, каждый элемент массива просматривается не более двух раз: один раз как начало последовательности и один раз как её продолжение.

Пространственная сложность: O(1), так как используется только фиксированное количество дополнительных переменных, независимо от размера входного массива. 

func findMaxLength(arr []int) int {
	var maxLength int
	for i := 0; i < len(arr)-1; i++ {
		left, right := i, i+1
		for right < len(arr) && arr[left] == arr[right] {
			right++
		}
		maxLength = max(maxLength, right-left)
		i = right - 1
	}
	return maxLength
}

Этот код реализует функцию intersect, которая находит пересечение двух целочисленных массивов nums1 и nums2. Пересечение включает все элементы, которые присутствуют в обоих массивах, с учетом их количества.

Алгоритм решения

  1. Создание хеш-таблицы (map) для подсчета элементов первого массива:
    • Проходим по nums1 и увеличиваем счетчик для каждого элемента в map.
  2. Поиск пересечения:
    • Проходим по nums2.
    • Если элемент присутствует в map и его счетчик больше 0:
      • Добавляем элемент в результат.
      • Уменьшаем счетчик элемента в map.
  3. Возвращаем результирующий массив.
  • Временная сложность: O(n + m)
    • n - длина nums1
    • m - длина nums2
    • Требуется один проход по каждому массиву
  • Пространственная сложность: O(min(n, m))
    • Для хранения map и результирующего массива
    • В худшем случае размер равен длине меньшего из двух массивов
func intersect(nums1 []int, nums2 []int) []int {
	// Создаем map для подсчета элементов в nums1
	count := make(map[int]int)
	for _, num := range nums1 {
		count[num]++
	}

	// Создаем слайс для результата
	result := []int{}

	// Проходим по nums2 и проверяем наличие элементов в map
	for _, num := range nums2 {
		if count[num] > 0 {
			result = append(result, num)
			count[num]--
		}
	}

	return result
}

Этот код реализует функцию merge, которая объединяет два отсортированных массива nums1 и nums2 в один отсортированный массив. Результат сохраняется в массиве nums1, который изначально имеет достаточно места для хранения всех элементов.

Алгоритм решения

  1. Инициализация указателей:
    • p1: указывает на последний элемент в nums1
    • p2: указывает на последний элемент в nums2
    • p: указывает на последнюю позицию в объединенном массиве
  2. Итерация с конца массивов:
    • Сравниваем элементы nums1[p1] и nums2[p2]
    • Больший элемент помещаем в позицию p массива nums1
    • Сдвигаем соответствующий указатель и p
  3. Продолжаем, пока не обработаем все элементы из nums2
  • Временная сложность: O(m+n)
    • m - количество элементов в nums1
    • n - количество элементов в nums2
    • Алгоритм проходит по всем элементам обоих массивов один раз
  • Пространственная сложность: O(1)
    • Алгоритм работает in-place, не используя дополнительной памяти
func merge(nums1 []int, m int, nums2 []int, n int) {
	// Указатели на последние элементы массивов
	p1 := m - 1    // для nums1
	p2 := n - 1    // для nums2
	p := m + n - 1 // для объединенного массива

	// Идем с конца массивов, заполняя nums1 с конца
	for p2 >= 0 {
		if p1 >= 0 && nums1[p1] > nums2[p2] {
			nums1[p] = nums1[p1]
			p1--
		} else {
			nums1[p] = nums2[p2]
			p2--
		}
		p--
	}
}

Этот код реализует функцию missingNumber, которая находит пропущенное число в последовательности от 0 до n, где n - длина входного массива nums. Предполагается, что в массиве nums содержатся все числа от 0 до n, кроме одного.

Алгоритм решения

  1. Инициализация переменных:
    • sum: сумма всех чисел от 0 до n (включительно)
    • res: сумма всех чисел в массиве nums
  2. Итерация по массиву:
    • Добавляем i к sum (учитывая числа от 0 до n-1)
    • Добавляем nums[i] к res
  3. Вычисление пропущенного числа:
    • Возвращаем разницу между sum и res
  • Временная сложность: O(n)
    • Где n - длина входного массива
    • Алгоритм проходит по массиву один раз
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительной памяти
func missingNumber(nums []int) int {
	sum := len(nums)
	res := 0
	for i := 0; i < len(nums); i++ {
		sum += i
		res += nums[i]
	}

	return sum - res
}

Этот код реализует функцию moveZeroes, которая перемещает все нули в конец массива nums, сохраняя относительный порядок ненулевых элементов.

Алгоритм решения

  1. Инициализация указателя nonZeroIndex:
    • Указывает на позицию, куда нужно поместить следующий ненулевой элемент
  2. Первый проход по массиву:
    • Если элемент не равен нулю, перемещаем его на позицию nonZeroIndex
    • Увеличиваем nonZeroIndex
  3. Второй проход по оставшейся части массива:
    • Заполняем все позиции от nonZeroIndex до конца массива нулями
  • Временная сложность: O(n)
    • Где n - длина входного массива
    • Алгоритм проходит по массиву дважды: один раз для перемещения ненулевых элементов и второй раз для заполнения нулями
  • Пространственная сложность: O(1)
    • Алгоритм работает in-place, не используя дополнительной памяти
func moveZeroes(nums []int) {
	nonZeroIndex := 0

	// Перемещаем все ненулевые элементы в начало массива
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[nonZeroIndex] = nums[i]
			nonZeroIndex++
		}
	}

	// Заполняем оставшуюся часть массива нулями
	for i := nonZeroIndex; i < len(nums); i++ {
		nums[i] = 0
	}
}

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

Алгоритм решения

  1. Инициализация:
    • Создаем результирующий массив той же длины, что и входной
    • Устанавливаем два указателя: left в начало и right в конец входного массива
  2. Итерация с конца результирующего массива:
    • Сравниваем абсолютные значения чисел на левом и правом указателях
    • Больший квадрат помещаем в текущую позицию результата
    • Сдвигаем соответствующий указатель
  3. Повторяем, пока не заполним весь результирующий массив
  • Временная сложность: O(n)
    • Где n - длина входного массива
    • Алгоритм проходит по всем элементам ровно один раз
  • Пространственная сложность: O(n)
    • Создается новый массив для хранения результата, длина которого равна длине входного массива 
func sortedSquares(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	left, right := 0, n-1

	for i := n - 1; i >= 0; i-- {
		if abs(nums[left]) > abs(nums[right]) {
			result[i] = nums[left] * nums[left]
			left++
		} else {
			result[i] = nums[right] * nums[right]
			right--
		}
	}

	return result
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Функция summaryRanges принимает отсортированный массив целых чисел и возвращает список строк, представляющих диапазоны последовательных чисел в этом массиве.

Алгоритм решения

  1. Проверка на пустой массив:
    • Если массив пуст, возвращаем пустой список строк
  2. Инициализация:
    • Создаем пустой список строк для результата
    • Инициализируем пустую строку current для хранения начала текущего диапазона
  3. Итерация по массиву:
    • Для каждого числа проверяем три случая:
      1. Не последний элемент и нет текущего диапазона
      2. Не последний элемент и есть текущий диапазон
      3. Последний элемент массива
    • В зависимости от случая, либо начинаем новый диапазон, либо завершаем текущий, либо добавляем одиночное число
  4. Формирование результата:
    • Добавляем сформированные диапазоны или одиночные числа в результирующий список
  • Временная сложность: O(n)
    • Где n - длина входного массива
    • Алгоритм проходит по всем элементам массива ровно один раз
  • Пространственная сложность: O(n)
    • В худшем случае (когда каждое число образует отдельный диапазон) результирующий список будет содержать n элементов 
func summaryRanges(nums []int) []string {
	if len(nums) == 0 {
		return []string{}
	}

	var res []string
	current := ""

	for i, num := range nums {
		switch {
		case i < len(nums)-1 && current == "":
			if num+1 == nums[i+1] {
				current = strconv.Itoa(num)
			} else {
				res = append(res, strconv.Itoa(num))
			}
		case i < len(nums)-1 && current != "":
			if num+1 != nums[i+1] {
				res = append(res, current+"->"+strconv.Itoa(num))
				current = ""
			}
		case i == len(nums)-1:
			if current != "" {
				res = append(res, current+"->"+strconv.Itoa(num))
			} else {
				res = append(res, strconv.Itoa(num))
			}
		}
	}

	return res
}

Функция twoSum находит два числа в массиве, сумма которых равна заданному целевому значению (target). Возвращает индексы этих двух чисел.

Алгоритм решения

  1. Инициализация:
    • Создаем пустую хеш-таблицу (map) для хранения чисел и их индексов
  2. Итерация по массиву:
    • Для каждого числа вычисляем его дополнение (complement) до целевого значения
    • Проверяем, есть ли дополнение в хеш-таблице
    • Если есть, возвращаем индексы текущего числа и его дополнения
    • Если нет, добавляем текущее число и его индекс в хеш-таблицу
  3. Если решение не найдено:
    • Возвращаем nil
  • Временная сложность: O(n)
    • Где n - количество элементов в массиве
    • Алгоритм проходит по массиву только один раз
  • Пространственная сложность: O(n)
    • В худшем случае хеш-таблица может содержать все n элементов массива
func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i, num := range nums {
		complement := target - num
		if j, ok := m[complement]; ok {
			return []int{j, i}
		}
		m[num] = i
	}

	return nil
}

Дан отсортированный по возрастанию массив целых чисел 'a' и целевое значение 'target'. Необходимо найти два индекса 0 ≤ l < r < n, такие что a[l] + a[r] == target. Если такая пара существует, нужно вернуть эти индексы. В противном случае вернуть признак отсутствия решения.

Алгоритм решения

  1. Инициализировать два указателя: left (в начале массива) и right (в конце массива).
  2. Пока left < right:
    • Вычислить сумму элементов a[left] и a[right].
    • Если сумма равна target, вернуть индексы left и right.
    • Если сумма меньше target, увеличить left.
    • Если сумма больше target, уменьшить right.
  3. Если цикл завершился без нахождения решения, вернуть признак отсутствия решения.
  • Временная сложность: O(n), где n - длина массива.
  • Пространственная сложность: O(1), используется константное дополнительное пространство. 
func twoSum(nums []int, target int) (int, int) {
    left, right := 0, len(nums)-1

    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            return left, right
        } else if sum < target {
            left++
        } else {
            right--
        }
    }

    // Если пара не найдена, возвращаем недопустимые индексы
    return -1, -1
}

Функция evalRPN вычисляет результат арифметического выражения, записанного в обратной польской нотации (RPN). В этой нотации операнды располагаются перед операторами.

Алгоритм решения

  1. Инициализация:
    • Создаем пустой стек для хранения чисел
  2. Итерация по токенам:
    • Если токен - число, добавляем его в стек
    • Если токен - оператор:
      • Извлекаем два последних числа из стека
      • Выполняем соответствующую операцию
      • Результат помещаем обратно в стек
  3. Завершение:
    • Возвращаем единственное число, оставшееся в стеке (результат вычисления)
  • Временная сложность: O(n)
    • Где n - количество токенов в входном массиве
    • Алгоритм проходит по каждому токену ровно один раз
  • Пространственная сложность: O(n)
    • В худшем случае стек может содержать все числа из входного массива
func evalRPN(tokens []string) int {
	stack := make([]int, 0)
	for _, token := range tokens {
		if num, err := strconv.Atoi(token); err == nil {
			stack = append(stack, num)
			continue
		}
		a, b := stack[len(stack)-2], stack[len(stack)-1]
		stack = stack[:len(stack)-2]

		switch token {
		case "+":
			stack = append(stack, a+b)
		case "-":
			stack = append(stack, a-b)
		case "*":
			stack = append(stack, a*b)
		case "/":
			stack = append(stack, a/b)
		}
	}

	return stack[0]
}

Функция searchRange находит начальную и конечную позиции заданного целевого значения в отсортированном массиве. Если целевое значение не найдено, возвращается [-1, -1].

Алгоритм решения

  1. Проверка на пустой массив:
    • Если массив пуст, возвращаем [-1, -1]
  2. Бинарный поиск:
    • Инициализируем указатели left и right на начало и конец массива
    • Выполняем бинарный поиск, пока left ≤ right
    • Если найдено целевое значение:
      • Расширяем диапазон влево и вправо, пока находим целевое значение
      • Возвращаем найденный диапазон
    • Если значение в середине меньше цели, сдвигаем left
    • Если значение в середине больше цели, сдвигаем right
  3. Если целевое значение не найдено, возвращаем [-1, -1]
  • Временная сложность:
    • В лучшем и среднем случае: O(log n) - благодаря бинарному поиску
    • В худшем случае: O(n) - когда все элементы равны целевому значению
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительной памяти
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}

	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2

		if nums[mid] == target {
			// считаем элементы слева и справа
			l, r := mid, mid
			for {
				if l >= 0 && nums[l] == target {
					l--
				}
				if r < len(nums) && nums[r] == target {
					r++
				}

				if (l < 0 || nums[l] != target) && (r == len(nums) || nums[r] != target) {
					return []int{l + 1, r - 1}
				}
			}
		}

		if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return []int{-1, -1}
}

Функция findClosestElements находит K ближайших элементов к заданному числу X в отсортированном массиве.

Алгоритм решения

  1. Проверка граничных условий:
    • Если длина массива меньше K или массив пуст, возвращаем весь массив
    • Если X меньше или равно первому элементу, возвращаем первые K элементов
    • Если X больше или равно последнему элементу, возвращаем последние K элементов
  2. Бинарный поиск:
    • Инициализируем левую границу поиска как 0, правую как len(arr) - K
    • Выполняем бинарный поиск, пока left < right:
      • Находим середину диапазона
      • Сравниваем расстояния от X до элементов arr[mid] и arr[mid+K]
      • Сдвигаем границы поиска в зависимости от результата сравнения
  3. Возвращаем подмассив длины K, начиная с найденной позиции
  • Временная сложность: O(log(n-k) + k)
    • log(n-k) - для бинарного поиска
    • k - для формирования результирующего массива
  • Пространственная сложность: O(k)
    • Для хранения результирующего массива
func findClosestElements(arr []int, k int, x int) []int {
	if len(arr) < k || len(arr) == 0 {
		return arr
	}

	left, right := 0, len(arr)-k // ставим окно поиска

	// Проверка граничных случаев
	if x <= arr[0] { // 0 элемент больше x то берём первые k элементов
		return arr[:k]
	}
	if x >= arr[len(arr)-1] { // если последний элемент больше x, то берём последние k элементов
		return arr[len(arr)-k:]
	}

	// Бинарный поиск
	for left < right {
		mid := left + (right-left)/2
		if x-arr[mid] > arr[mid+k]-x { // если x больше среднего, двигаем в правую часть
			left = mid + 1
		} else {
			right = mid
		}
	}
	return arr[left : left+k]
}

Функция groupAnagrams группирует анаграммы из заданного списка строк. Анаграммы - это слова, состоящие из одних и тех же букв, но в разном порядке.

Алгоритм решения

  1. Инициализация:
    • Создаем пустую карту (map) для хранения групп анаграмм
  2. Обработка каждой строки:
    • Преобразуем строку в слайс рун
    • Сортируем символы строки
    • Используем отсортированную строку как ключ в карте
    • Добавляем исходную строку в соответствующую группу в карте
  3. Формирование результата:
    • Преобразуем карту в слайс слайсов строк
  4. Возвращаем результат
  • Временная сложность: O(n * k * log(k))
    • n - количество строк в исходном слайсе
    • k - максимальная длина строки
    • Сортировка каждой строки занимает O(k * log(k))
  • Пространственная сложность: O(n * k)
    • Для хранения всех строк в карте и результирующем слайсе
func groupAnagrams(strs []string) [][]string {
	groups := make(map[string][]string)

	for _, str := range strs {
		// Сортируем символы строки для получения ключа
		chars := []rune(str)
		slices.Sort(chars)
		key := string(chars)

		// Добавляем строку в соответствующую группу
		groups[key] = append(groups[key], str)
	}

	// Преобразуем map в slice
	result := make([][]string, 0, len(groups))
	for _, group := range groups {
		result = append(result, group)
	}

	return result
}

Функция longestSubarray находит длину самого длинного подмассива, состоящего только из единиц, после удаления одного элемента из исходного массива.

Алгоритм решения

  1. Инициализация переменных:
    • left - левая граница окна
    • zeros - количество нулей в текущем окне
    • maxLen - максимальная длина найденного подмассива
  2. Проход по массиву с использованием техники "скользящего окна":
    • Расширяем окно вправо
    • Если встречаем ноль, увеличиваем счетчик нулей
    • Если в окне больше одного нуля, сужаем окно слева
    • Обновляем максимальную длину подмассива
  3. Обработка особого случая:
    • Если максимальная длина равна длине исходного массива, вычитаем 1
  4. Возвращаем результат
  • Временная сложность: O(n)
    • n - количество элементов в массиве
    • Каждый элемент обрабатывается не более двух раз (при расширении и сужении окна)
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительной памяти
func longestSubarray(nums []int) int {
	left, zeros, maxLen := 0, 0, 0

	for right := 0; right < len(nums); right++ {
		if nums[right] == 0 {
			zeros++
		}

		// Сужаем окно, если в нем больше одного нуля
		for zeros > 1 {
			if nums[left] == 0 {
				zeros--
			}
			left++
		}

		// Обновляем максимальную длину
		// Вычитаем 1, так как нужно удалить один элемент
		maxLen = max(maxLen, right-left)
	}

	// Если maxLen равен длине массива, возвращаем maxLen-1,
	// иначе возвращаем maxLen
	if maxLen == len(nums) {
		return maxLen - 1
	}
	return maxLen
}

Функция longestOnes находит длину самого длинного подмассива, состоящего только из единиц, после замены не более k нулей на единицы.

Алгоритм решения

  1. Инициализация переменных:
    • left - левая граница окна
    • maxOnes - максимальная длина найденного подмассива
  2. Проход по массиву с использованием техники "скользящего окна":
    • Расширяем окно вправо
    • Если встречаем ноль, уменьшаем k
    • Если k становится отрицательным, сдвигаем левую границу окна
    • Обновляем максимальную длину подмассива
  3. Возвращаем результат
  • Временная сложность: O(n)
    • n - количество элементов в массиве
    • Каждый элемент обрабатывается не более двух раз (при расширении и сужении окна)
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительной памяти
func longestOnes(nums []int, k int) int {
	left, maxOnes := 0, 0
	for right := 0; right < len(nums); right++ {
		if nums[right] == 0 {
			k--
		}
		if k < 0 {
			if nums[left] == 0 {
				k++
			}
			left++
		}
		maxOnes = max(maxOnes, right-left+1)
	}
	return maxOnes
}

Функция maxDistToClosest находит максимальное расстояние, на котором можно сесть от ближайшего человека в ряду сидений, представленном массивом seats, где 1 означает занятое место, а 0 - свободное.

Алгоритм решения

  1. Инициализация переменных:
    • n - длина массива seats
    • left - индекс последнего занятого места слева (изначально -1)
    • maxDist - максимальное найденное расстояние
  2. Проход по массиву seats:
    • Если встречаем занятое место (1):
      • Если это первое занятое место, проверяем расстояние от начала ряда
      • Иначе вычисляем расстояние между текущим и предыдущим занятым местом
      • Обновляем maxDist, если найдено большее расстояние
      • Обновляем left
  3. После прохода проверяем расстояние от последнего занятого места до конца ряда
  4. Возвращаем максимальное найденное расстояние
  • Временная сложность: O(n)
    • n - длина массива seats
    • Алгоритм проходит по массиву ровно один раз
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительных переменных
func maxDistToClosest(seats []int) int {
	n := len(seats)
	left := -1 // индекс последнего занятого места слева
	maxDist := 0

	for i := 0; i < n; i++ {
		if seats[i] == 1 {
			// Если это первое занятое место, проверяем расстояние от начала
			if left == -1 {
				maxDist = i
			} else {
				// Иначе проверяем расстояние между двумя занятыми местами
				maxDist = max(maxDist, (i-left)/2)
			}
			left = i
		}
	}

	// Проверяем расстояние от последнего занятого места до конца
	maxDist = max(maxDist, n-1-left)

	return maxDist
}

Функция findMedianSortedArrays находит медиану двух отсортированных массивов nums1 и nums2.

Алгоритм решения

  1. Обработка краевых случаев:
    • Если один из массивов пустой, возвращается медиана другого массива
  2. Оптимизация:
    • Обеспечение того, что nums1 - более короткий массив
  3. Бинарный поиск по более короткому массиву:
    • Поиск правильной точки разделения в обоих массивах
    • Сравнение элементов на границах разделения
    • Корректировка точки разделения в зависимости от сравнения
  4. Вычисление медианы:
    • Для четного общего количества элементов - среднее двух средних элементов
    • Для нечетного - максимальный из двух "левых" элементов
  • Временная сложность: O(log(min(m, n)))
    • m и n - длины массивов nums1 и nums2 соответственно
    • Бинарный поиск выполняется по более короткому массиву
  • Пространственная сложность: O(1)
    • Используется постоянное количество дополнительной памяти
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// Обработка случая, когда один из массивов пустой
	if len(nums1) == 0 {
		return medianOfArray(nums2)
	}
	if len(nums2) == 0 {
		return medianOfArray(nums1)
	}

	// Мы всегда работаем с меньшим массивом как с nums1 для оптимизации.
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}
	l1, l2 := len(nums1), len(nums2)

	// бинарный поиск
	left, right := 0, l1
	for left <= right {
		cur1 := (left + right) / 2
		cur2 := (l1+l2+1)/2 - cur1
		/* Вычисляем соответствующую точку разделения для второго массива: cur2 = (l1 + l2 + 1) / 2 - cur1
		Это обеспечивает, что левая часть обоих массивов всегда содержит (l1 + l2 + 1) / 2 элементов */
		first1 := getVal(nums1, cur1, math.MaxInt)
		last1 := getVal(nums1, cur1-1, math.MinInt)
		first2 := getVal(nums2, cur2, math.MaxInt)
		last2 := getVal(nums2, cur2-1, math.MinInt)

		switch {
		case last1 <= first2 && last2 <= first1:
			// чётное кол-во или нет
			if (l1+l2)%2 == 0 {
				return (float64(max(last1, last2)) + float64(min(first1, first2))) / 2.0
			}
			return float64(max(last1, last2))
		case last1 > first2:
			right = cur1 - 1
		default:
			left = cur1 + 1
		}
	}

	return 0.0
}

/*
*
Функция getVal используется для безопасного получения этих значений,
возвращая минимальное или максимальное целое число, если индекс выходит за границы массива.
*/
func getVal(nums []int, index int, defaultVal int) int {
	if index < 0 || index >= len(nums) {
		return defaultVal
	}
	return nums[index]
}

func medianOfArray(nums []int) float64 {
	n := len(nums)
	if n%2 == 0 {
		return float64(nums[n/2-1]+nums[n/2]) / 2.0
	}
	return float64(nums[n/2])
}

Функция findNonOverlappingIntervals принимает массив интервалов и возвращает новый массив, где все пересекающиеся интервалы объединены.

Алгоритм решения

  1. Проверка на пустой входной массив
  2. Сортировка интервалов по начальной точке (при равенстве - по конечной точке)
  3. Итерация по отсортированным интервалам:
    • Если текущий интервал пересекается с предыдущим, объединяем их
    • Если не пересекается, добавляем предыдущий интервал в результат и начинаем новый
  4. Добавление последнего обработанного интервала в результат
  • Временная сложность: O(n log n)
    • Сортировка интервалов занимает O(n log n)
    • Последующая итерация по интервалам занимает O(n)
  • Пространственная сложность: O(n)
    • В худшем случае, когда нет пересечений, результирующий массив будет такого же размера, как входной 
func findNonOverlappingIntervals(intervals [][]int) [][]int {
	if len(intervals) == 0 {
		return [][]int{}
	}

	slices.SortFunc(intervals, func(i, j []int) int { // log n
		switch {
		case i[0] == j[0] && i[1] == j[1]:
			return 0
		case i[0] < j[0] || (i[0] == j[0] && i[1] < j[1]):
			return -1
		default:
			return 1
		}
	})

	var resultIntervals [][]int
	currentInterval := intervals[0]
	for _, interval := range intervals[1:] {
		switch {
		case interval[0] <= currentInterval[1]: // [1, 3] in [2, 6]
			currentInterval[1] = max(currentInterval[1], interval[1])
		case interval[0] > currentInterval[1]: // [1, 3] in [5, 7]
			resultIntervals = append(resultIntervals, currentInterval)
			currentInterval = interval
		}
	}
	resultIntervals = append(resultIntervals, currentInterval)

	return resultIntervals
}

Функция MergeKSortedArrays объединяет K отсортированных массивов в один отсортированный массив.

Алгоритм решения

  1. Инициализация результирующего массива и массива указателей для каждого входного массива
  2. Итеративный процесс:
    • Поиск минимального элемента среди текущих элементов всех массивов
    • Добавление найденного минимального элемента в результат
    • Продвижение указателя для массива, из которого был взят минимальный элемент
  3. Повторение процесса, пока все элементы не будут обработаны
  • Временная сложность: O(N * k)
    • N - общее количество элементов во всех массивах
    • k - количество массивов
    • На каждой итерации происходит поиск минимума среди k элементов
  • Пространственная сложность: O(N + k)
    • O(N) для результирующего массива
    • O(k) для массива указателей
func MergeKSortedArrays(arrays [][]int) []int {
	result := make([]int, 0)
	points := make([]int, len(arrays))

	for {
		minVal := 101
		minIdx := -1

		// Ищем минимальный индекс
		for i, arr := range arrays {
			if points[i] < len(arr) &&
				(minIdx < 0 || arr[points[i]] < minVal) {
				minVal = arr[points[i]]
				minIdx = i
			}
		}

		// Если не нашли минимальный элемент, значит все массивы обработаны
		if minIdx == -1 {
			break
		}

		// Добавляем минимальный элемент в результат и двигаем указатель
		result = append(result, minVal)
		points[minIdx]++
	}

	return result
}

Функция productExceptSelf вычисляет для каждого элемента массива произведение всех остальных элементов, не используя операцию деления.

Алгоритм решения

  1. Инициализация результирующего массива answer
  2. Вычисление префиксных произведений:
    • Проход слева направо
    • Каждый элемент answer[i] содержит произведение всех элементов слева от nums[i]
  3. Вычисление суффиксных произведений и формирование окончательного результата:
    • Проход справа налево
    • Умножение каждого элемента answer[i] на суффиксное произведение
    • Обновление суффиксного произведения
  • Временная сложность: O(n)
    • Два прохода по массиву: один слева направо, другой справа налево
  • Пространственная сложность: O(1)
    • Не считая выходной массив, используется только одна дополнительная переменная 
func productExceptSelf(nums []int) []int {
	n := len(nums)
	answer := make([]int, n)

	// Инициализируем первый элемент answer как 1
	answer[0] = 1

	// Вычисляем префиксное произведение
	for i := 1; i < n; i++ {
		answer[i] = answer[i-1] * nums[i-1]
	}

	// Вычисляем суффиксное произведение и одновременно обновляем answer
	suffixProduct := 1
	for i := n - 1; i >= 0; i-- {
		answer[i] *= suffixProduct
		suffixProduct *= nums[i]
	}

	return answer
}

Функция search выполняет поиск заданного элемента target в повернутом отсортированном массиве nums.

Алгоритм решения

  1. Инициализация указателей left и right на начало и конец массива
  2. Бинарный поиск с модификацией:
    • Нахождение среднего элемента mid
    • Если nums[mid] == target, возвращаем mid
    • Определение, какая половина массива отсортирована:
      • Если левая половина отсортирована (nums[left] <= nums[mid]):
        • Если target находится в левой половине, сужаем поиск влево
        • Иначе сужаем поиск вправо
      • Если правая половина отсортирована:
        • Если target находится в правой половине, сужаем поиск вправо
        • Иначе сужаем поиск влево
  3. Если элемент не найден, возвращаем -1
  • Временная сложность: O(log n)
    • Используется модифицированный бинарный поиск
    • На каждой итерации область поиска уменьшается вдвое
  • Пространственная сложность: O(1)
    • Используется фиксированное количество дополнительных переменных
func search(nums []int, target int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2

		if nums[mid] == target {
			return mid
		}

		// Левая половина отсортирована
		if nums[left] <= nums[mid] {
			if target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else { // Правая половина отсортирована
			if target > nums[mid] && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return -1 // Элемент не найден
}

Функция subarraySum подсчитывает количество подмассивов в заданном массиве nums, сумма элементов которых равна заданному значению k.

Алгоритм решения

  1. Инициализация переменных:
    • count - счетчик подходящих подмассивов
    • sum - текущая кумулятивная сумма
    • sumCounts - карта для хранения количества встреченных кумулятивных сумм
  2. Итерация по элементам массива:
    • Обновление кумулятивной суммы
    • Проверка наличия комплементарной суммы sum-k в карте
    • Увеличение счетчика на количество найденных комплементарных сумм
    • Обновление количества текущей кумулятивной суммы в карте
  3. Возврат общего количества найденных подмассивов
  • Временная сложность: O(n)
    • n - количество элементов в массиве
    • Один проход по всем элементам массива
  • Пространственная сложность: O(n)
    • В худшем случае, когда все кумулятивные суммы уникальны
    • Использование карты для хранения кумулятивных сумм
func subarraySum(nums []int, k int) int {
	count := 0
	sum := 0
	sumCounts := make(map[int]int)
	sumCounts[0] = 1 // Инициализируем для случая, когда подмассив начинается с начала массива

	for _, num := range nums {
		sum += num
		if cnt, exists := sumCounts[sum-k]; exists {
			count += cnt
		}
		sumCounts[sum]++
	}

	return count
}

Функция subarraysDivByK подсчитывает количество подмассивов в заданном массиве nums, сумма элементов которых делится на заданное число k.

Алгоритм решения

  1. Инициализация переменных:
    • count - карта для хранения количества встреченных остатков от деления
    • sum - текущая кумулятивная сумма
    • result - счетчик подходящих подмассивов
  2. Итерация по элементам массива:
    • Обновление кумулятивной суммы
    • Вычисление остатка от деления суммы на k (с обработкой отрицательных чисел)
    • Увеличение результата на количество ранее встреченных подмассивов с таким же остатком
    • Обновление количества текущего остатка в карте
  3. Возврат общего количества найденных подмассивов
  • Временная сложность: O(n)
    • n - количество элементов в массиве
    • Один проход по всем элементам массива
  • Пространственная сложность: O(min(n, k))
    • В худшем случае хранятся k различных остатков в карте
    • Количество уникальных остатков ограничено значением k
func subarraysDivByK(nums []int, k int) int {
	count := make(map[int]int)
	count[0] = 1 // Инициализируем для случая, когда вся префиксная сумма делится на k
	sum := 0
	result := 0

	for _, num := range nums {
		sum += num
		remainder := (sum%k + k) % k // Обрабатываем отрицательные числа
		result += count[remainder]
		count[remainder]++
	}

	return result
}

Дан массив целых чисел. Необходимо найти в нем такой индекс, что сумма элементов слева от него равна сумме элементов справа от него. Если такого индекса нет, вернуть -1. Важно решить задачу за O(N) времени и за O(1) памяти.

Примеры:

Входной массив: [1, 7, 3, 6, 5, 6]

Результат: 3 (сумма слева: 1+7+3=11, сумма справа: 5+6=11)

Входной массив: [1, 2, 3]

Результат: -1 (нет индекса равновесия)

Алгоритм решения

  1. Проверяем, что массив не пуст. Если массив пуст, возвращаем -1.
  2. Вычисляем общую сумму всех элементов массива.
  3. Инициализируем переменную leftSum = 0 для хранения суммы элементов слева от текущего индекса.
  4. Проходим по массиву и для каждого индекса i:
    • Вычисляем сумму элементов справа как rightSum = totalSum - leftSum - nums[i]
    • Проверяем, равна ли сумма элементов слева (leftSum) сумме элементов справа (rightSum)
    • Если равна, возвращаем текущий индекс i
    • Обновляем leftSum, добавляя к ней текущий элемент для следующей итерации
  5. Если после проверки всех индексов точка равновесия не найдена, возвращаем -1.

Временная сложность: O(N), где N - длина массива.

Мы делаем два прохода по массиву: один для вычисления общей суммы и один для поиска индекса равновесия. Оба прохода линейны, поэтому общая временная сложность составляет O(N).

Пространственная сложность: O(1).

Мы используем только несколько переменных (totalSum, leftSum, rightSum) независимо от размера входного массива, поэтому пространственная сложность постоянна.

func FindEquilibriumIndex(nums []int) int {
    n := len(nums)
    if n == 0 {
        return -1
    }

    // Вычисляем общую сумму всех элементов
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }

    // Проходим по массиву и проверяем каждый индекс
    leftSum := 0
    for i := 0; i < n; i++ {
        // Правая сумма = общая сумма - левая сумма - текущий элемент
        rightSum := totalSum - leftSum - nums[i]

        // Если левая сумма равна правой, нашли индекс равновесия
        if leftSum == rightSum {
            return i
        }

        // Обновляем левую сумму для следующей итерации
        leftSum += nums[i]
    }

    // Если индекс равновесия не найден
    return -1
}

Дан массив целых чисел. Необходимо найти максимальный по длине подотрезок (непрерывный подмассив), в котором сумма всех элементов является четным числом. Если таких подотрезков несколько, нужно выбрать наибольший по длине. Если подотрезков с четной суммой нет, вернуть 0.

Примеры:

Входной массив: [1, 2, 3, 4, 5]

Результат: 4 (подотрезок [2, 3, 4, 5] имеет сумму 14, которая четная)

Входной массив: [2, 4, 6, 8]

Результат: 4 (весь массив имеет четную сумму 20)

Входной массив: [1, 3, 5, 7]

Результат: 0 (нет подотрезков с четной суммой)

Алгоритм решения

Алгоритм основан на следующем математическом наблюдении: если префиксные суммы двух подмассивов имеют одинаковый остаток при делении на 2, то сумма элементов между ними будет четной.

  1. Проверяем, что массив не пуст. Если массив пуст, возвращаем 0.
  2. Создаем карту для хранения индекса первого вхождения каждого остатка от деления префиксной суммы на 2.
  3. Инициализируем карту с остатком 0 и индексом -1 (это нужно для обработки случая, когда префиксная сумма сама по себе четная).
  4. Проходим по массиву, накапливая текущую сумму и вычисляя остаток от деления на 2.
  5. Для каждой позиции проверяем:
    • Если текущий остаток уже встречался ранее, значит между текущей позицией и первым вхождением этого остатка сумма четная.
    • Вычисляем длину этого подотрезка и обновляем максимальную длину.
    • Если остаток встречается впервые, запоминаем его позицию.
  6. Возвращаем найденную максимальную длину.

Временная сложность: O(N), где N - длина массива.

Мы делаем один проход по массиву, и все операции внутри цикла (доступ к карте, вычисление остатка) выполняются за O(1).

Пространственная сложность: O(1).

Несмотря на использование карты, в ней будет максимум 2 элемента (для остатков 0 и 1), поэтому пространственная сложность константна.

func FindMaxEvenSubsegment(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    // Храним индекс первого вхождения остатка от деления на 2
    // Для четной суммы (остаток 0) и нечетной суммы (остаток 1)
    firstOccurrence := map[int]int{
        0: -1, // Инициализируем для четной суммы как -1 (до начала массива)
    }

    maxLength := 0
    currentSum := 0

    for i := 0; i < n; i++ {
        // Обновляем текущую сумму и вычисляем остаток от деления на 2
        currentSum += nums[i]
        remainder := currentSum % 2

        // Если такой остаток уже встречался, значит между текущей позицией
        // и первым вхождением этого остатка сумма четная
        if idx, exists := firstOccurrence[remainder]; exists {
            length := i - idx
            maxLength = max(maxLength, length)
        } else {
            // Запоминаем первое вхождение этого остатка
            firstOccurrence[remainder] = i
        }
    }

    return maxLength
}

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

Алгоритм решения

  1. Инициализируем два указателя: left и right, определяющие текущий подмассив.
  2. Создаем два монотонных стека: minStack для минимальных элементов и maxStack для максимальных.
  3. Двигаем правый указатель right по массиву:
    • Обновляем minStack, удаляя элементы, большие текущего.
    • Обновляем maxStack, удаляя элементы, меньшие текущего.
    • Добавляем текущий индекс в оба стека.
  4. Если разница между максимальным и минимальным элементом превышает k:
    • Двигаем левый указатель left вправо.
    • Обновляем стеки, удаляя элементы, вышедшие за пределы текущего окна.
  5. Обновляем максимальную длину подмассива.
  6. Повторяем шаги 3-5, пока не достигнем конца массива.
  • Использование монотонных стеков позволяет эффективно отслеживать минимальные и максимальные элементы в текущем окне.
  • Алгоритм работает за линейное время, что делает его эффективным для больших массивов.
  • Решение использует технику "скользящего окна" с динамическим изменением его размера.
  • Подход позволяет решить задачу за один проход по массиву.
  • Временная сложность: O(n), где n - длина входного массива. Каждый элемент добавляется и удаляется из стеков не более одного раза.
  • Пространственная сложность: O(n) в худшем случае, когда все элементы могут оказаться в стеках. 
func maxSubarrayWithDiffK(arr []int, k int) int {
	n := len(arr)
	maxLen := 0
	left := 0
	minStack := []int{}
	maxStack := []int{}

	for right := 0; right < n; right++ {
		// Обновляем минимальный стек
		for len(minStack) > 0 && arr[minStack[len(minStack)-1]] > arr[right] {
			minStack = minStack[:len(minStack)-1]
		}
		minStack = append(minStack, right)

		// Обновляем максимальный стек
		for len(maxStack) > 0 && arr[maxStack[len(maxStack)-1]] < arr[right] {
			maxStack = maxStack[:len(maxStack)-1]
		}
		maxStack = append(maxStack, right)

		// Проверяем разницу между максимальным и минимальным элементом
		for arr[maxStack[0]]-arr[minStack[0]] > k {
			left++
			if left > minStack[0] {
				minStack = minStack[1:]
			}
			if left > maxStack[0] {
				maxStack = maxStack[1:]
			}
		}

		// Обновляем максимальную длину
		maxLen = max(maxLen, right-left+1)
	}

	return maxLen
}

Дан массив целых чисел nums и целевое значение target. Необходимо найти такую тройку чисел в массиве с различными индексами, что их сумма наиболее близка к целевому значению target. Требуется вернуть саму сумму трех чисел.

Примеры:

Пример 1:

Вход: nums = [-1, 2, 1, -4], target = 1

Выход: 2

Пояснение: Сумма -1 + 2 + 1 = 2 наиболее близка к целевому значению 1.

Пример 2:

Вход: nums = [0, 0, 0], target = 1

Выход: 0

Пояснение: Сумма 0 + 0 + 0 = 0 наиболее близка к целевому значению 1.

Алгоритм решения

Для решения этой задачи используется подход с сортировкой массива и техникой двух указателей:

  1. Проверяем, что в массиве достаточно элементов (не менее 3). Если элементов меньше, возвращаем 0.
  2. Сортируем массив для эффективного поиска с помощью двух указателей.
  3. Инициализируем переменную closestSum начальным значением (сумма первых трех элементов).
  4. Вычисляем начальную минимальную разницу minDiff между closestSum и целевым значением.
  5. Перебираем первый элемент тройки в цикле:
    • Пропускаем дубликаты для оптимизации (если текущий элемент равен предыдущему).
    • Устанавливаем два указателя: left (сразу после текущего элемента) и right (конец массива).
    • Пока left < right:
      • Вычисляем текущую сумму трех элементов: nums[i] + nums[left] + nums[right].
      • Вычисляем разницу между текущей суммой и целевым значением.
      • Если нашли точное совпадение (разница = 0), сразу возвращаем результат.
      • Если текущая разница меньше минимальной, обновляем minDiff и closestSum.
      • Двигаем указатели: если текущая сумма меньше целевого значения, увеличиваем left, иначе уменьшаем right.
  6. Возвращаем найденную ближайшую сумму closestSum.

Временная сложность: O(n²), где n - размер массива.

Сортировка массива занимает O(n log n), а алгоритм с двумя указателями требует O(n²) операций в худшем случае.

Пространственная сложность: O(log n) или O(1), в зависимости от реализации сортировки.

Помимо входного массива, мы используем только константное количество дополнительных переменных.

func ThreeSumClosest(nums []int, target int) int {
    n := len(nums)
    if n < 3 {
        return 0 // Недостаточно элементов
    }

    // Сортируем массив для использования двух указателей
    sort.Ints(nums)

    // Инициализируем переменную для хранения ближайшей суммы
    // с максимально возможным значением разницы
    closestSum := nums[0] + nums[1] + nums[2]
    minDiff := math.Abs(float64(closestSum - target))

    // Перебираем первый элемент тройки
    for i := 0; i < n-2; i++ {
        // Пропускаем дубликаты для первого элемента
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        // Используем два указателя для поиска оставшихся двух элементов
        left, right := i+1, n-1

        for left < right {
            currentSum := nums[i] + nums[left] + nums[right]
            currentDiff := math.Abs(float64(currentSum - target))

            // Если нашли точное совпадение, сразу возвращаем результат
            if currentSum == target {
                return currentSum
            }

            // Обновляем ближайшую сумму, если текущая разница меньше
            if currentDiff < minDiff {
                minDiff = currentDiff
                closestSum = currentSum
            }

            // Двигаем указатели в зависимости от текущей суммы
            if currentSum < target {
                left++
            } else {
                right--
            }
        }
    }

    return closestSum
}

Даны два массива целых чисел A и B. Необходимо найти минимальное значение абсолютной разницы |A[i] - B[j]| между любыми элементами этих массивов.

Примеры:

Пример 1:

Вход: A = {0}, B = {1}

Выход: 1

Пояснение: Единственная возможная разница |0-1| = 1.

Пример 2:

Вход: A = {10, 0, 2}, B = {5, 100, 12}

Выход: 2

Пояснение: Минимальная абсолютная разница достигается для пары (10, 12): |10-12| = 2.

Алгоритм решения

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

  1. Сортируем оба массива A и B
  2. Устанавливаем два указателя: i на начало массива A и j на начало массива B
  3. Пока оба указателя не достигли конца своих массивов:
    • Вычисляем абсолютную разницу между текущими элементами |A[i] - B[j]|
    • Обновляем минимальную разницу, если нашли меньшую
    • Двигаем указатель на массив с меньшим текущим элементом

Временная сложность: O(n log n + m log m), где n и m - размеры массивов A и B соответственно.

  • Сортировка массива A: O(n log n)
  • Сортировка массива B: O(m log m)
  • Проход по массивам с двумя указателями: O(n + m)

Пространственная сложность: O(1) дополнительной памяти (не считая входных массивов).

func FindMinAbsDifference(A, B []int) int {
    if len(A) == 0 || len(B) == 0 {
        return 0
    }

    // Сортируем оба массива
    sort.Ints(A)
    sort.Ints(B)

    minDiff := math.MaxInt32
    i, j := 0, 0

    // Используем два указателя для прохода по массивам
    for i < len(A) && j < len(B) {
        diff := int(math.Abs(float64(A[i] - B[j])))
        minDiff = min(minDiff, diff)

        // Двигаем указатель на меньший элемент
        if A[i] < B[j] {
            i++
        } else {
            j++
        }
    }

    return minDiff
}

Дан отсортированный по возрастанию массив уникальных целых чисел, который был циклически сдвинут на неизвестное количество позиций. Требуется найти индекс заданного элемента в этом массиве или вернуть -1, если элемент отсутствует.

Алгоритм решения

  1. Найти точку сдвига в массиве с помощью бинарного поиска.
  2. Выполнить бинарный поиск на всем массиве, учитывая сдвиг при вычислении среднего элемента.
  • Временная сложность: O(log N), где N - количество элементов в массиве.
  • Пространственная сложность: O(1), используется константное дополнительное пространство. 
func findTarget(nums []int, target int) int {
    if len(nums) == 0 {
        return -1
    }

    // Находим точку сдвига
    k := findShiftPoint(nums)

    // Выполняем бинарный поиск на всем массиве
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        realMid := (mid + k) % len(nums)  // Учитываем сдвиг

        if nums[realMid] == target {
            return realMid
        }

        if nums[realMid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

// Находит точку сдвига в массиве
func findShiftPoint(nums []int) int {
    left, right := 0, len(nums)-1

    // Если массив не был сдвинут
    if nums[left] < nums[right] {
        return 0
    }

    for left <= right {
        mid := left + (right-left)/2

        // Проверяем, является ли mid точкой сдвига
        if mid < len(nums)-1 && nums[mid] > nums[mid+1] {
            return mid + 1
        }

        if nums[mid] >= nums[0] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return 0
}

Даны два массива целых чисел A и B одинаковой длины N. Для каждого K от 1 до N необходимо подсчитать количество чисел, которые встречаются как в первых K элементах массива A, так и в первых K элементах массива B. Результат нужно вернуть в виде массива длины N+1, где элемент с индексом K содержит количество общих чисел для первых K элементов обоих массивов.

Алгоритм решения

  1. Инициализировать массив результатов и хеш-таблицу для отслеживания встречаемости чисел.
  2. Для каждого K от 1 до N:
    • Обновить хеш-таблицу для K-го элемента массива A.
    • Обновить хеш-таблицу для K-го элемента массива B.
    • Подсчитать количество общих элементов для первых K элементов.
    • Записать результат в массив результатов.
  3. Вернуть массив результатов.
  • Временная сложность: O(N), где N - длина массивов.
  • Пространственная сложность: O(N) для хранения хеш-таблицы и массива результатов.
func countCommonPrefixes(a, b []int) []int {
    n := len(a)
    result := make([]int, n+1)
    has := make(map[int]int)

    for k := 1; k <= n; k++ {
        // Обновляем хеш-таблицу для текущего элемента a[k-1]
        if _, exists := has[a[k-1]]; !exists {
            has[a[k-1]] = 0
        }
        if has[a[k-1]] == 1 {
            has[a[k-1]] = 2
        } else {
            has[a[k-1]] = 0
        }

        // Обновляем хеш-таблицу для текущего элемента b[k-1]
        if _, exists := has[b[k-1]]; !exists {
            has[b[k-1]] = 1
        }
        if has[b[k-1]] == 0 {
            has[b[k-1]] = 2
        }

        // Подсчитываем общие элементы
        count := 0
        for i := 0; i < k; i++ {
            if has[a[i]] == 2 {
                count++
            }
        }
        result[k] = count
    }

    return result
}

Дан массив целых чисел. Необходимо "сжать" его, представив последовательные числа в виде диапазонов. Каждый диапазон должен быть представлен либо одним числом (если диапазон состоит из одного числа), либо парой чисел (начало и конец диапазона). Результат должен быть представлен в виде массива массивов.

Вход: [-3, -10, 1, -2, 2, 3, 5]
Выход: [[-10], [-3, -2], [1, 3], [5]]

Алгоритм решения

  1. Создать словарь (map) для хранения всех уникальных чисел из входного массива.
  2. Пока словарь не пуст:
    • Выбрать произвольное число из словаря.
    • Найти максимальный непрерывный диапазон чисел, содержащих выбранное число.
    • Добавить найденный диапазон в результат.
    • Удалить все числа найденного диапазона из словаря.
  3. Вернуть полученный результат.

Временная сложность: O(n), где n - количество элементов в исходном массиве.
Пространственная сложность: O(n) для хранения словаря и результата. 

func CompressArray(arr []int) [][]int {
    // Создаем словарь для хранения элементов массива
    dict := make(map[int]bool)
    for _, num := range arr {
        dict[num] = true
    }

    result := [][]int{}

    for len(dict) > 0 {
        // Выбираем произвольный ключ из словаря
        var key int
        for k := range dict {
            key = k
            break
        }

        // Ищем максимальные l и r
        l, r := key, key
        for dict[l-1] {
            l--
        }
        for dict[r+1] {
            r++
        }

        // Добавляем результат
        if l == r {
            result = append(result, []int{l})
        } else {
            result = append(result, []int{l, r})
        }

        // Удаляем найденные числа из словаря
        for i := l; i <= r; i++ {
            delete(dict, i)
        }
    }

    return result
}

Даны два массива целых чисел: a и b. Необходимо найти количество подотрезков массива a, которые являются подпоследовательностями массива b.

Алгоритм решения

  1. Инициализируем счетчик count для подсчета подходящих подотрезков.
  2. Перебираем все возможные левые границы l в массиве a.
  3. Для каждой левой границы:
    • Инициализируем счетчик cnt для отслеживания совпадений с элементами b.
    • Проходим по элементам a, начиная с позиции l, сравнивая их с элементами b.
    • Если находим совпадение, увеличиваем cnt и переходим к следующему элементу b.
    • Если cnt достигает длины b, значит, мы нашли полную подпоследовательность:
      • Добавляем к count количество оставшихся элементов в a.
      • Прерываем внутренний цикл и переходим к следующей левой границе.
  4. Возвращаем итоговое значение count.
  • Временная сложность: O(n * m), где n - длина массива a, m - длина массива b. В худшем случае, для каждого элемента a мы можем пройти по всем элементам b.
  • Пространственная сложность: O(1), так как мы используем только несколько дополнительных переменных, независимо от размера входных данных. 
func countSubarrays(a, b []int) int {
	count := 0
	n := len(a)
	m := len(b)

	for l := 0; l < n; l++ {
		cnt := 0
		for i, j := l, 0; i < n && j < m; i++ {
			if a[i] == b[j] {
				j++
				cnt++
			}
			if cnt == m {
				count += n - i
				break
			}
		}
	}

	return count
}

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

Алгоритм решения

  1. Инициализируем переменные:
    • lastOne: позиция последней встреченной единицы (изначально -1)
    • maxDistance: максимальное найденное расстояние
    • result: позиция нуля с максимальным расстоянием
  2. Проходим по массиву слева направо:
    • Если встречаем единицу:
      • Если это первая единица, обрабатываем случай начальных нулей
      • Иначе вычисляем расстояние до предыдущей единицы
      • Если новое расстояние больше максимального, обновляем maxDistance и result
    • Обновляем позицию последней единицы
  3. После прохода проверяем случай конечных нулей
  4. Возвращаем найденную позицию нуля
  • Временная сложность: O(n), где n - длина массива. Алгоритм проходит по массиву ровно один раз.
  • Пространственная сложность: O(1), так как используется фиксированное количество дополнительных переменных, независимо от размера входных данных. 
func findMaxDistanceZero(arr []int) int {
	n := len(arr)
	lastOne := -1
	maxDistance := 0
	result := 0

	for i := 0; i < n; i++ {
		if arr[i] == 1 {
			if lastOne == -1 {
				// Обработка случая, когда последовательность начинается с нуля
				maxDistance = i
				result = 0
			} else {
				// Вычисление расстояния между текущей единицей и предыдущей
				distance := (i - lastOne) / 2
				if distance > maxDistance {
					maxDistance = distance
					result = lastOne + distance
				}
			}
			lastOne = i
		}
	}

	// Обработка случая, когда последовательность заканчивается нулем
	if n-1-lastOne > maxDistance {
		result = n - 1
	}

	return result
}

Дан массив целых чисел длины n > 1. Необходимо найти минимальное произведение, которое можно получить из двух чисел массива с уникальными позициями.

Алгоритм решения

  1. Проверяем длину массива. Если она меньше или равна 1, возвращаем 0, так как невозможно выбрать два уникальных числа.
  2. Инициализируем переменные для хранения двух максимальных (max1, max2) и двух минимальных (min1, min2) чисел.
  3. Проходим по массиву один раз, обновляя значения max1, max2, min1 и min2.
  4. После прохода по массиву проверяем три условия:
    • Если min1 ≤ 0 и max1 ≥ 0, возвращаем min1 * max1 (случай с отрицательными и неотрицательными числами).
    • Если min1 > 0 (все числа положительные), возвращаем min1 * min2.
    • В противном случае (все числа отрицательные), возвращаем max1 * max2.
  • Временная сложность: O(n), где n - длина входного массива. Мы проходим по массиву только один раз.
  • Пространственная сложность: O(1), так как мы используем фиксированное количество дополнительных переменных независимо от размера входного массива. 
func minProduct(arr []int) int {
	if len(arr) <= 1 {
		return 0 // Невозможно выбрать два уникальных числа
	}

	max1, max2 := math.MinInt32, math.MinInt32
	min1, min2 := math.MaxInt32, math.MaxInt32

	for _, num := range arr {
		// Обновляем максимальные числа
		if num > max1 {
			max2 = max1
			max1 = num
		} else if num > max2 {
			max2 = num
		}

		// Обновляем минимальные числа
		if num < min1 {
			min2 = min1
			min1 = num
		} else if num < min2 {
			min2 = num
		}
	}

	// Проверяем условия и возвращаем результат
	if min1 <= 0 && max1 >= 0 {
		return min1 * max1
	} else if min1 > 0 {
		return min1 * min2
	} else {
		return max1 * max2
	}
}

Дано N пар чисел a_i и b_i, представляющих отрезки на числовой прямой от (a_i, 0) до (1, b_i). Требуется найти количество отрезков, которые не пересекаются с другими отрезками в этом множестве.

Алгоритм решения

  1. Создаем структуру Segment для представления отрезков с полями a и b.
  2. Формируем слайс отрезков из входных данных a и b.
  3. Сортируем отрезки по возрастанию координаты a (начальной точки).
  4. Инициализируем счетчик непересекающихся отрезков (count) и переменную для хранения максимальной конечной точки (maxB).
  5. Проходим по отсортированному массиву отрезков слева направо:
    • Если конечная точка текущего отрезка (b) больше maxB, увеличиваем count и обновляем maxB.
  6. Возвращаем значение count как результат.
  • Временная сложность: O(N log N), где N - количество отрезков. Основной вклад вносит сортировка отрезков.
  • Пространственная сложность: O(N) для хранения отсортированного массива отрезков. 
type Segment struct {
	a, b int
}

func countNonIntersectingSegments(a, b []int) int {
	n := len(a)
	segments := make([]Segment, n)
	for i := 0; i < n; i++ {
		segments[i] = Segment{a[i], b[i]}
	}

	// Сортируем отрезки по координате a
	sort.Slice(segments, func(i, j int) bool {
		return segments[i].a < segments[j].a
	})

	count := 0
	maxB := 0

	for i := 0; i < n; i++ {
		if segments[i].b > maxB {
			count++
			maxB = segments[i].b
		}
	}

	return count
}

Дан массив, состоящий только из 0 и 1. Требуется найти такую позицию для размещения нуля, чтобы минимальное расстояние до ближайшей единицы было максимальным.

Алгоритм решения

  1. Инициализируем переменные:
    • lastOne: индекс последней встреченной единицы (изначально -1)
    • maxDistance: максимальное найденное расстояние
    • optimalPosition: оптимальная позиция для нуля
  2. Проходим по массиву слева направо:
    • Если встречаем 1:
      • Если это первая единица, сравниваем расстояние от начала массива
      • Иначе вычисляем расстояние между текущей и предыдущей единицей
    • Обновляем maxDistance и optimalPosition, если найдено большее расстояние
    • Обновляем lastOne
  3. После прохода проверяем расстояние от последней единицы до конца массива
  4. Возвращаем optimalPosition
  • Временная сложность: O(n), где n - длина входного массива. Алгоритм проходит по массиву ровно один раз.
  • Пространственная сложность: O(1), так как используется только фиксированное количество дополнительных переменных, независимо от размера входного массива. 
func findOptimalZeroPosition(arr []int) int {
    n := len(arr)
    lastOne := -1
    maxDistance := 0
    optimalPosition := 0

    for i := 0; i < n; i++ {
        if arr[i] == 1 {
            if lastOne == -1 {
                // Первая единица в массиве
                if i > maxDistance {
                    maxDistance = i
                    optimalPosition = 0
                }
            } else {
                // Расстояние между текущей и предыдущей единицей
                distance := (i - lastOne) / 2
                if distance > maxDistance {
                    maxDistance = distance
                    optimalPosition = (i + lastOne) / 2
                }
            }
            lastOne = i
        }
    }

    // Проверяем расстояние от последней единицы до конца массива
    if n - 1 - lastOne > maxDistance {
        maxDistance = n - 1 - lastOne
        optimalPosition = n - 1
    }

    return optimalPosition
}