1_Two_Sum.py

# 1. 两数之和
# 给定一个整数数组 nums 和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
# 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
# 你可以按任意顺序返回答案。

# 示例 1：
# 输入：nums = [2,7,11,15], target = 9
# 输出：[0,1]
# 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

# 示例 2：
# 输入：nums = [3,2,4], target = 6
# 输出：[1,2]

# 示例 3：
# 输入：nums = [3,3], target = 6
# 输出：[0,1]

# 提示：
#     2 <= nums.length <= 104
#     -109 <= nums[i] <= 109
#     -109 <= target <= 109
#     只会存在一个有效答案

# 进阶：你可以想出一个时间复杂度小于 O(n²) 的算法吗？

from typing import List
# 暴力破解
# 时间复杂度：O(N²)，其中N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
# 空间复杂度：O(1)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

# 建立哈希表查找
# 时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元素x，我们可以O(1)地寻找target - x
# 空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销
# 算法推演：num = [3,2,4] target = 6
# step 1: i = 0, num= 3, 6 - 3 = 3, h为空没有3, 保存h = <3, 0>
# step 2: i = 1, num= 2, 6 - 2 = 4, h = <3, 0>没有4, 更新h = <3, 0>, <2, 1>
# step 3: i = 2, num= 4, 6 - 4 = 2, h中<2, 1>有2，返回[1, 2]
class Solution1:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h = {}
        for i, num in enumerate(nums):
            # 去num中找target - num[i]
            if target - num in h.keys():
                return [h[target - num], i]
            # value-key而不是key-value初始化哈希表
            h[nums[i]] = i
        return []
s = Solution()
num = [2,7,11,15]
target = 9
print(f"num = {num}")
print(f"target = {target}")
print(s.twoSum(num,target))
print("")
num = [3,2,4]
target = 6
print(f"num = {num}")
print(f"target = {target}")
print(s.twoSum(num,target))
print("")
num = [3,3]
target = 6
print(f"num = {num}")
print(f"target = {target}")
print(s.twoSum(num,target))
print("")
num = [3,2,3]
target = 6
print(f"num = {num}")
print(f"target = {target}")
print(s.twoSum(num,target))