阅读 265

小白刷力扣之两数之和

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

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

我这里还为自己立下了一个小目标,就是每道算法题,都会尝试用 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 = [1324]
>>> list(enumerate(l))
[(01), (13), (22), (34)]
>>>
复制代码

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

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

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