[数据结构与算法]力扣LeetCode 热题HOT 100 #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(n2) 的算法吗？

根据题目描述，此题是非常简单的

题解1：暴力枚举

无for循环版(不推荐)非常冗余，但是能帮助理解原理

"""
from typing import List
"""
def twoSum(nums: List[int], target: int) -> List[int]:
    num1 = 0
    num2 = 1
    while True:
        if nums[num1] + nums[num2] == target:
            return [num1, num2]
        elif num2 == len(nums) - 1:
            num1 += 1
            num2 = num1 + 1
        else:
            num2 += 1
        if num1 == len(nums) - 1:
            break
    return [None]

num1和num2是列表索引，分别从 0和1开始，每轮循环来逐一遍历列表并验证一次当前的整数相加是否为target

有for循环版(推荐)也是官方题解了

"""
from typing import List
"""
def twoSum(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return [None]

?同理

缺点:

暴力枚举时间复杂度比较高，此题中是O(n^2)，所以随着列表的扩大，只会让你等待计算机算出答案的时间越来越长

题解2：哈希表(散列表)

原理:

数据结构 Hash表（哈希表）_积跬步 至千里-CSDN博客_哈希表

(24条消息) hash算法原理详解_至道-CSDN博客_hash算法

(24条消息) hash算法详解_xu_dongdong的博客-CSDN博客_hash算法详解

(24条消息) 浅谈算法和数据结构：哈希表_一个程序猿的故事-CSDN博客_数据结构算法哈希

在Python中已经实现了，它就是字典

由于哈希表的特性，我们可以使用key-value来解决时间复杂度过高的问题

"""
from typing import List
"""
def twoSum(nums: List[int], target: int) -> List[int]:
    h = {}
    for i, num in enumerate(nums):
        if target - num in h:
            return [h[target - num], i]
        h[num] = i
    return [None]

首先创建一个 h 字典，用 enumerate 方法给 nums 列表创建索引与列表元素的一一对应，每论循环拿出一个索引 i，列表元素 num，然后判断 target - num 这个 key 是否存在于字典中，找到就直接返回，找不到就将目前的 num 作为 key，i 作为 value 来添加入 h 字典中，直到最终找到答案返回。

之所以能这样编写代码就是利用了 10 - 2 = 8，10 - 8 = 2 这种简单的想法，要找的数没有先后之分只要差值存在于字典的 key 当中，就能用 O(1) 的时间复杂度将其找到并把对应的 value 找出来。

此代码算上for循环，总体时间复杂度只有O(n)，大大提高了效率，是此题的最优解