Решение задач Python

Введение

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

Two Sum

Задача с сайта leetcode.com. Уровень сложности Easy.

Условие

Имеется массив целых чисел nums и целочисленная цель.

Нужно вернуть индексы двух чисел сумма которых равна цели.

У каждый задачи будет ровно одно решение, один и тот же индекс дважды возвращать нельзя.

Порядок индексов не важен.

Пример 1: Входные данные: nums = [2, 7, 11, 15], цель = 9 Выходные данные: [0, 1] Пояснение: Поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1]. Пример 2: Входные данные: числа = [3, 2, 4], цель = 6 Выходные данные: [1, 2] Пример 3: Входные данные: числа = [3, 3], цель = 6 Выходные данные: [0, 1] Ограничения: 2 <= цифры.длина <= 104 -109 <= числа[i] <= 109 -109 <= target <= 109 Существует только один правильный ответ.

Цель - предложить алгоритм, менее сложный по времени, чем O(n2)?

Решение

Решение сложности O(n2) это простой перебор по списку. Например, такой

class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: le = len(nums) for i in range(0, le): for j in range(i + 1, le): if nums[i] + nums[j] == target: return [i, j]

В качестве тестов используем следующие наборы данных

… a = Solution() print(a.twoSum([2, 7, 11, 15], 9)) # [0, 1] print(a.twoSum([3, 2, 4], 6)) # [1, 2] print(a.twoSum([3, 3], 6)) # [0, 1] print(a.twoSum([0, 4, 3, 0], 0)) # [0, 3] print(a.twoSum([-3, 4, 3, 90], 0)) # [0, 2]

По мнению Leetcode.com это решение использует 17.2 MB памяти и выполняется за 1625 ms.

Сократить Runtime можно используя метод index() для поиска второго индекса мы будем использовать параметр start.

Сперва рассмотрим решение без использования range и len(nums)

class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: for n in nums: try: i = nums.index(n) t = nums.index(target - n, i + 1) return [i, t] except ValueError: pass

Этот вариант имеет Runtime 641 ms.

# Решение 1 class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: for i in range(0, len(nums)): try: j = nums.index(target - nums[i], i + 1) return [i, j] except ValueError: pass

Это решение получилось ещё быстрее - 314 ms по версии leetcode при похожем расходе памяти.

Самым быстрым вариантом по версии leetcode.com оказался тот, где индексирование применяется не вперёд по списку а назад, по пройденным элементам.

Для этого нужно создать свой словарь который для большей понятности переходящим с других языков программирования, назовём hash_table

# Решение 2 class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: hash_table = {} for i, num in enumerate(nums): if target - num in hash_table: return [hash_table[target - num], i] hash_table[num] = i

Если верить сайту leetcode.com Решение 2 однозначно лучше чем Решение 1.

Проверим эффективность алгоритмов самостоятельно

import time class Timer: def __enter__(self): self.start = time.perf_counter() return self def __exit__(self, exc_type, exc_val, exc_tb): self.stop = time.perf_counter() self.elapsed = self.stop - self.start class SolutionLC: def twoSum(self, nums: list[int], target: int) -> list[int]: hash_table = {} for i, num in enumerate(nums): if target - num in hash_table: return [hash_table[target - num], i] hash_table[num] = i class SolutionAO: def twoSum(self, nums: list[int], target: int) -> list[int]: for i in range(0, len(nums)): try: j = nums.index(target - nums[i], i + 1) return [i, j] except ValueError: pass tthousand = list(range(0, 10000)) def perf_check(nums, target, solution): t = Timer() with t: print(solution.twoSum(nums, target)) print(f"elapsed time {t.elapsed}") if __name__ == "__main__": print("lc") perf_check(tthousand, 19997, SolutionLC()) # [9998, 9999] perf_check(tthousand, 1, SolutionLC()) # [0, 1] print("ao") perf_check(tthousand, 19997, SolutionAO()) # [9998, 9999] perf_check(tthousand, 1, SolutionAO()) # [0, 1]

lc [9998, 9999] elapsed time 0.0006979999598115683 [0, 1] elapsed time 4.800036549568176e-06 ao [9998, 9999] elapsed time 0.2148211000021547 [0, 1] elapsed time 6.800051778554916e-06

Если искомая пара расположена в самом конце, постоянное индексирование по списку сильно медленнее поиска по словарю.

Если искомая пара находится в начале списка - Решение 1, которое постоянно ищет вперёд, проигрывает несущественно, но тем не менее тоже медленнее.

Так как поиск по словарю быстрее

Автор статьи: Андрей Олегович