专栏首页萝卜大杂烩小白刷力扣之两数之和

小白刷力扣之两数之和

作为一个半路出家的算法小白,最近尝试着刷一下力扣,来扩展些思维,毕竟总是写一些复杂度非常高的代码也不是那么回事。

当然作为一个绝对有自知之明的人,这种时候一定是从最简单的算法题开始,先看看自己的斤两再说吧。

我这里还为自己立下了一个小目标,就是每道算法题,都会尝试用 Python 和 Java 两种语言来求解,并且会顺带这分析算法题背后的知识点,毕竟解题是一方面,背后的知识还是要弄清楚的,希望自己能够坚持下去。

两数之和

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

先来看看最为暴力的两层循环解法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

其实这种解法不用说太多,无非就是循环两次列表,如果在内循环中找到 target 值,则返回对应的索引。

那么来看看这种简单粗暴的方法成绩怎么样呢

执行时间真的是惨不忍睹啊,这个击败比率都快赶上我的电脑开机速度的战斗值了。

优化一

我们可以把给定的列表进行排序,然后通过比较首尾两数之和与 target 之间的大小来判定目标索引的位置,这种方法只需要进行一次排序就可以实现。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_id = [k for k,v in sorted(enumerate(nums), key=lambda k: k[1])]
        head = 0
        tail = len(nums) - 1
        sum = nums[sorted_id[head]] + nums[sorted_id[tail]]
        while sum != target:
            if sum > target:
                tail -= 1
            else:
                head += 1
            sum = nums[sorted_id[head]] + nums[sorted_id[tail]]
        return [sorted_id[head], sorted_id[tail]]

如果当前两数之和大于 target,则移动尾部索引;反之则移动首部索引。

这种方法的关键就是获取到排序后原列表的元素索引,对应的代码为

sorted_id = [k for k,v in sorted(enumerate(nums), key=lambda k: k[1])]

这句话比较绕,我们来具体看下: 比如有列表 l = [1, 3, 2, 4],那么通过上述代码后,会得到列表 sorted_id = [0, 2, 1, 3],即实际上我们可以隐性的知道排序后的列表为 [1, 2, 3, 4] 即 [sorted_id[0], sorted_id[1], sorted_id[2], sorted_id[3]]。

关键函数说明: enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标。

>>> l = [1, 3, 2, 4]
>>> list(enumerate(l))
[(0, 1), (1, 3), (2, 2), (3, 4)]
>>>

当然,这里还有一种更为简单的排序方法

sorted_id = sorted(range(len(nums)), key=lambda k: nums[k])

以上两段排序代码都是我们在该算法题中可以额外学习到的技能。

优化二

第二种优化方式为利用 Python 的字典,来保存列表数值与对应的索引。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for index, num in enumerate(nums):
            gap_num = target - num
            if gap_num in map:
                return [map[gap_num], index]
            map[num] = index
        return None

可以看到,还是通过函数 enumerate 获取列表的数值与索引,然后依次放置字典中,先进行 if 判断,如果存在则直接返回中止程序。

其实 Python 中的字典就是一种哈希表,那么它与 Java 中的 HashMap 有什么区别呢?

其实 Python 中的字典也是哈希表的一种,与 Java 语言中的 HashMap 是同一种数据结构,所不同的是字典在遇到哈希冲突时,采用开放寻址法,而 HashMap 采用的是链表法。

我们先来看下什么是哈希表:

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 记录的存储位置=f(关键字),这里的对应关系f称为散列函数,又称为哈希(Hash函数)。

哈希表 hashtable(key,value) 就是把 Key 通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将 value 存储在以该数字为下标的数组空间里。

那么 Java 中的 HashMap 使用的链表法是什么意思呢,就是说当哈希冲突时,会在数组的对应索引下挂一个链表来存储冲突的值,而 Python 字典的开放寻址法则为当哈希冲突时,通过某些规划把该值存储到其他索引下。

优化三

最后再来看看 Java 语言的解法,最好的办法就是利用 HashMap 来解决该题。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i])){
                indexs[0] = i;
                indexs[1] = hash.get(nums[i]);
                return indexs;
            }
            hash.put(target - nums[i], i);
        }
        return indexs;
    }
}

与 Python 的字典解法类似,都是通过依次循环,把对应的数值与索引放入哈希表中然后进行判断。

通过上面的分析可以看出,当我们在试图解决一道问题的时候,我们是可以扩展出很多其他知识的,一起加油吧!

本文分享自微信公众号 - 萝卜大杂烩(luobodazahui),作者:小白刷力扣

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 把英雄分类,看 Python 带你上王者

    王者荣耀这么久了,还没上王者?哈哈哈,看过来,是不是对英雄理解的不够透彻呢,是不是还没有很好的为英雄分类呢,今天就来看看英雄分类

    周萝卜
  • 从头搭建一个在线聊天室(三)

    随着我们项目功能越来越多,把所有的逻辑代码都写在一个文件里已经不太合适了,下面就通过 flask 的工厂模式,把项目代码拆分开。

    周萝卜
  • 圣诞来临,爬取女神美图放松下

    大神徐麟(公众号“数据森麟”)写过一篇爬取懂球帝女神大会数据的文章,非常棒,自己闲来无事,也尝试着做一下。(关键是年尾了,墙裂需要女神们来养养眼

    周萝卜
  • 最大子序列和(leetcode)

    euclid
  • 牛客练习赛23 D

      利用全排列函数加vector数组,开十个vector,存a到i字母出现的位置,最后每个vector再push_back(字符串长度加一)作为结束标志。

    用户2965768
  • leetcode 1-Two Sum问题

    问题: 给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但...

    CristianoC
  • 2019 HDU 多校赛第三场 HDU 6609 Find the answer(树状数组+二分答案 查询前k小)

    题意: 多组询问,n个人,值m, 接下来n个值,要求当前值加上前面尽量多的值之和小于等于 m ,问前面要去掉几个值

    用户2965768
  • C/C++条件表达式

    C/C++条件表达式使用三目运算符 ?:完成,适当条件下可与 if else 语句相互替换。 条件表达式优点在于可直接返回表达式运算的结果。

    英雄爱吃土豆片
  • 【CCF】日期计算

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    喜欢ctrl的cxk
  • 【2020HBU天梯赛训练】7-26 链表去重

    给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另...

    韩旭051

扫码关注云+社区

领取腾讯云代金券