LeetCode—两数之和(python篇)
下面是道力扣题,接下来会教给大家三种方式完成,以后会专门出一个目录用python解题。

其实这道题乍一看还是比较简单的,事实上确实也是比较基础的一道题,但是也不免会有一些不屑一顾且上手就犯怵的理论大师,当然也希望自己的这几种解题方式可以帮助到各位小”猿“
暴力解法
接下来是第一种"暴力解法"
代码:
# 这道力扣题就是让我们找到两数之和可以等于target即可
# !!!注意 是返回两数的位置 而不是结果!!!
nums = [2,7,11,15]
target = 9
# 何为暴力解法 简单来说就是直接循环出结果 来我们直接开始第一步
for i in range(len(nums)):
for j in range(i+1,len(nums)):
# 注意这里的i+1,i+1在这里的作用是避免重复数组再次出现
if nums[i] + nums[j] == target:
print([i,j])
# 启动程序运行我们可以看到最终的结果是[0,1]
在以上解法中有一个点是我们需要注意的第二个循环里面的 i+1 是什么
举个例子:
小明,小红,小美,三个人要两人为一个组合
组法:【小明,小红】,【小明,小美】,【小红,小美】
【小红,小明】,【小红,小美】,【小明,小美】
【小美,小红】,【小美,小明】,【小明,小红】
一共九种组法,但是我们能看到,实际上就三种组合其他的都是重复的
重复的只是顺序但是人没变,同理,在暴力解法里面添加 i+1 可以避免重复打印。
添加 i+1 之后组合:【小明,小红】,【小明,小美】,【小红,小美】
所以大家一定要理解着去用“暴力解法”。
哈希表优化
第二种解法“哈希表优化”,听名字是不是很高大尚,有些小"猿"可能就犯怵了,我都没听过怎么来理解呢,下面由我带大家学一下哈希表优化法是怎么优化出最终的结果的。
代码:
# 好的,现在我们先把代码按照逻辑写出来,然后我们看结果再来Dbug大家就清晰了!
# 还以nums=[2,7,11,15],target=9 为例
nums = [2,7,11,15]
target = 9
#首先我们先创建哈希表 表格,数据库一般都是字典形式,所以在这里大家别用错类型了
hash_map = {}
# 创建完之后我们还是将数据循环到哈希表中
for i,num in enumerate(nums):
complement = target - num
if complement in hash_map:
print([hash_map[complement],i])
hash_map[num] = i
哈希表格最终存入的内容:
这里老师这个数组是老师测试随便写的 别因为数组被老师误导了
下面教大家是怎么得到最后的表格的:
哈希表的作用:
hash_map 存储了已经遍历过的数字及其索引。
查找 complement:
在遍历 nums 时,计算当前数字 num 需要的 complement(即 target - num)。
如果 complement 已经在 hash_map 中,说明之前已经有一个数字可以和当前 num 配对,
使得它们的和等于 target。
此时,直接返回 [hash_map[complement], i](即 complement 的索引和当前 num 的索引)。
顺序存储:
由于是顺序遍历,hash_map[complement] 一定在 i 之前,因此不会重复计算。
下面就是Dbug环节:
大家主要观察变化每个变量的变化,比如Dbug之前哈希表中是空的

Dbug一遍之后的表格:
记住我们的数组 nums = 【2,7,11,15】 target = 9

很直观的可以看到第一次循环,是将数组【2】以及他索引位置【0】按照【2:0】格式存储到哈希表中了,然后我们继续Dbug一直到结束。

我们可以看到Dbug完之后可以很清晰的看到表格中存到的数据,到这里相信大家也看懂了,如果还是有点迷迷糊糊 可以翻到上面的哈希表格每一步的操作都在表格中体现了
排序+双向指针法:
第三种,看着难其实就是基础的循环叠算,先解释一下什么是双向指针法
双向指针法(通俗易懂解释法):
双向指针就是给定一个有序数组和一个目标值,找出两个数的和等于目标值。
我们需要注意的是 有序数组 ,规则如下:
左指针从最左开始,右指针从最右开始。
如果两数之和小于目标值,左指针右移。
如果两数之和大于目标值,右指针左移。
直到找到和为目标值的两个数。
代码:
# 先排序,再双向,找到合适就停止
# 我给大家把数组的索引写一下 【0,1,2,3】 0对应的是2 【0:2,1:7,2:11,3:15】
nums = [2,7,11,15]
target = 9
# 先排序
nums_sorted = sorted(nums)
# 再双向(设置指针,我们就叫它 左和右)
left,right = 0 , len(nums_sorted)-1
# 这里解释一下,计算机语言是从0开始数的,所以最左边的我们设定为0,最右边的我们就要减1
# 定义好之后我们就要让两个指针开始工作了
while left < right:
current_sum = nums_sorted[left] + nums_sorted[right]
if current_sum == target:
index1 = nums.index(nums_sorted[left])
index2 = nums.index(nums_sorted[right],index1 + 1)
print([left,right])
break
elif current_sum < target:
left += 1
else:
right -=1
现在我们开始拆解代码:
循环开始为什么左边要小于右边呢?
答:因为排序之后顺序是从小到大的,而且双向指针就是从两边出发,所以左边的一定要在右边的左侧 给循环添加的条件:即 Left < Right
current_sum 是什么呢?
答:是左指针和右指针的和 因为是从两边出发,我们要找的是target 两个指针每走一步都要计算一下。
判断 current_sum == target是什么意思?
答: 这里是当左指针和右指针等于我们最终值的时候退出指针(目的达到了)。
目的达到之后:
我们就要确定这俩目标的索引值是多少 所以我们 需要定义两个变量 index1,2 来存储两个目标的索引值
index2 = nums.index(nums_sorted[right],index1 + 1)中的 index1+1 是什么呢?
答:因为我们刚开始的时候给右指针设置的是索引值是最大的【3:15】,按照题目要求是返回两个不同的索引,所以需要跳过 index1 之后的重复搜索。
当然其实大家也看到了里面还有个判断条件,下面就是给大家解释最终的判断条件是什么。
elif 指的是 当俩指针和小于目标的时候 说明需要增大俩指针的和所以移动 Left 向右移动也就是 left += 1
同理 else 指的是 当俩指针和大于目标的时候 说明需要减小俩指针的和所以移动 Right向左移动 也就是 right -= 1
好了 今天是我们讲解 力扣(LeetCode)的第一课,大家如果喜欢多多点赞,多多关注,你们的点赞和关注就是我创作的动力!
更多推荐

所有评论(0)