/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
codes/python/chapter_searching/two_sum.py
42 строки
1 KB
Yudong Jin
Some improvements (#1073)
07 фев 2024, 17:21
Не верифицирован
07 фев 2024, 17:21
a005c6e
Код
Авторство
О чём код?
""" File: two_sum.py Created Time: 2022-11-25 Author: krahets (krahets@163.com) """ def two_sum_brute_force(nums: list[int], target: int) -> list[int]: """方法一：暴力枚举""" # 两层循环，时间复杂度为 O(n^2) for i in range(len(nums) - 1): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return [] def two_sum_hash_table(nums: list[int], target: int) -> list[int]: """方法二：辅助哈希表""" # 辅助哈希表，空间复杂度为 O(n) dic = {} # 单层循环，时间复杂度为 O(n) for i in range(len(nums)): if target - nums[i] in dic: return [dic[target - nums[i]], i] dic[nums[i]] = i return [] """Driver Code""" if __name__ == "__main__": # ======= Test Case ======= nums = [2, 7, 11, 15] target = 13 # ====== Driver Code ====== # 方法一 res: list[int] = two_sum_brute_force(nums, target) print("方法一 res =", res) # 方法二 res: list[int] = two_sum_hash_table(nums, target) print("方法二 res =", res)