美文网首页
Day 8 两数之和

Day 8 两数之和

作者: 快乐的老周 | 来源:发表于2020-05-30 09:13 被阅读0次

```
'''

Day 8 打卡题:两数之和

首先看下题目描述:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

题目参考链接:https://leetcode-cn.com/problems/two-sum

考察知识点:数组,哈希表(字典)

请补充完整如下代码:

class Solution:

      def twoSum(self, nums: List[int], target: int) -> List[int]:

这道题目大家仔细思考下,想办法写出尽可能高效的代码。提示:牺牲空间换取时间

'''

class Solution:

      def twoSum1(self, nums, target): #使用hash

          d = {}

          for index, num in enumerate(nums):

              if num in d:

                  return [d.get( num ),index]

              else:

                  d[target-num] = index

      def twoSum2(self, nums, target): #使用list

          l = []

          for index, num in enumerate(nums):

              if num in l:

                  return [l.index(num), index]

              else:

                  l.append(target - num)

def test_twoSum():

    s = Solution()

    assert s.twoSum1([2,7,11,15],9)==[0,1]

    assert s.twoSum2([2,7,11,15],9)==[0,1]

```

知道想法和可以做出来是两件事,这道题以前做过,自己想到了暴力法, hashmap的做法也看过高手的解法,敲过,但今天又卡住了。

学算法,对我这种没有天赋的人(大多数人是没有天赋,不是天生就会,就能做好的),就是日攻一卒。

算法里可以用空间换时间,学习中就是用平时的时间换精进的程度。

暴力法,一个一个算,肯定是不合算的,因为可能会试多次不同的组合。无论我们是否做算法题,都应该注意,不要重复计算,否则效率一定低。

用什么方法可以不算很多次呢,那就应该算一次,记住,下一次就不用再计算了。

用list, hash都可以用来“记住”很多东西:

我们可以用list来记住我们需要的值,常规的list是一维的,只能记住我们需要的结果,记不住位置,而我们可以使用list的index位置属性来查询这是第几个元素。

而hash可以同时记住我们需要的值和index。从效率上来看,hash比list查询起来会更快(这只是我的感觉,list是要遍历的,大佬知道的话说说看原理)

相关文章

  • Day 8 两数之和

    ```''' Day 8 打卡题:两数之和 首先看下题目描述: 给定一个整数数组 nums 和一个目标值 targ...

  • leecode刷题(8)-- 两数之和

    leecode刷题(8)-- 两数之和 两数之和 描述: 给定一个整数数组 nums 和一个目标值 target,...

  • 两数之和(golang)

    原题:两数之和 关联:两数之和 II - 输入有序数组(golang)两数之和 IV - 输入 BST(golang)

  • 两数之和 II - 输入有序数组(golang)

    原题:两数之和 II - 输入有序数组 关联:两数之和(golang)两数之和 IV - 输入 BST(golan...

  • 浅入浅出实现一个异步求和函数

    简化:两数之和 我们先来简单的实现一个异步两数之和函数 加深:多数之和 上面我们实现了两数之和,然后扩展到多数之和...

  • 55.算法->两数之和

    day7:两数之和[https://leetcode-cn.com/problems/two-sum/](简单)思...

  • 两数之和,三数之和

    转载:https://www.cnblogs.com/DarrenChan/p/8871495.html 1. 两...

  • 两数之和&三数之和&四数之和&K数之和

    今天看了一道谷歌K数之和的算法题,忽然想起来之前在力扣上做过2、3、4数之和的题,觉得很有必要来整理一下。其实2、...

  • algrithrom

    求和问题,双指针解决 done 两数之和 三数之和 最接近三数之和 四数之和 链表反转问题 done 链表反转 链...

  • 「算法」两数之和 & 两数之和 II

    00001 两数之和 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只...

网友评论

      本文标题:Day 8 两数之和

      本文链接:https://www.haomeiwen.com/subject/dwzqzhtx.html