# @lc app=leetcode.cn id=1 lang=python3
# [1] 两数之和
# @lc code=start
class Solution:
def bruteForcetwoSum(self, nums: List[int], target: int) -> List[int]:
"""
暴力遍历法
Time complexity : O(n^2)
Space complexity: O(1)
"""
for i_first, v_first in enumerate(nums):
for i_second, v_second in enumerate(nums[(i_first+1):]):
if v_first + v_second == target:
return([i_first, i_second+i_first+1])
def onePassHashTabletwoSum(self, nums: List[int], target: int) -> List[int]:
"""
One-pass Hash Table:
Time complexity : O(n)
Space complexity: O(n)
"""
hash_table = {}
for index, value in enumerate(nums):
if target - value in hash_table.keys():
return [hash_table[target-value], index
hash_table[value] = index
# @lc code=end
# 解题思路
# 1.考察知识点
# 暴力遍历
# 暴力遍历法，直观、是最为直接能想到的方法
# 进度时间短、重业务逻辑处理的代码
# 性能要求低的代码（例如重渲染不重代码性能的前端、移动端）
# 哈希搜索
# 哈希搜索
# 主要是利用了哈希查询的特性，完全无冲突，则查询时间复杂度为O(1)
# One-pass Hash Table写法的特点是仅用一次循环就解决问题，在循环的同时将元素放入map。这样就无需考虑“数组中同一个元素在答案里不能重复出现”的情景
# 2.约束
# a) 2 <= nums.length <= 103
# b) -10^9 <= nums[i] <= 10^9
# c) -10^9 <= target <= 10^9
# 以上三项约束实际上是编程语言的数据类型的边界，所以无需特别处理
# d) 只会存在一个有效答案
# return值为[x,y]一维两元数组
# e) 数组中同一个下标的元素在答案里不能重复出现。
# return值中不存在[nums[x],nums[x]]的形式
# d,e两项约束需要在代码中进行规避
leetcode-两数之和 python
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 两数交集 例如: 给定nums1=[1, 2, 2, 1],nums2=[2, 2], 返回[2, 2] 答： c...
- 题目： 解法： 1. 暴力解法 这是最最容易想到的方法了......先用遍历一遍中的每一个元素，然后再看元素与后面...
- 1.两数之和 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数...
