下面是道力扣题,接下来会教给大家三种方式完成,以后会专门出一个目录用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)的第一课,大家如果喜欢多多点赞,多多关注,你们的点赞和关注就是我创作的动力!


                

Logo

北京人形旗下天工造物具身智能开源社区,聚焦具身天工与慧思开物两大平台

更多推荐