leetcode-两数之和 python

# @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两项约束需要在代码中进行规避