【简单算法】1.两数之和,给定整数数组和目标值,找出数组中2数之和等于目标值的元素

接触了代码,那么算法始终是绕不开的一个重点。

算法对于开发人员,在日常之中的作用很大,但是对于测试人员来说,实际编码中用到的似乎不是很多。
不过,现在大厂的测试开发的面试,算法是必考的,而且这也的确是你的代码功底的一项重要体现,学学没坏处。

【简单算法】1.两数之和,给定整数数组和目标值,找出数组中2数之和等于目标值的元素

关于算法的基础知识,之前自己也买过书,但是学习的断断续续的,练习刷题就更加稀少了。
所以,打算日后做一个【简单算法】的记录:

  • 第一,是为了梳理解题思路,加深巩固。
  • 第二,在学习解题的过程中,将薄弱的代码环节、算法基础补全。
  • 第三,算是对算法练习的一个督促。

题目来自LeetCode传送门,有兴趣的童鞋可以到上面刷题练习。

一、题目:两数之和

描述

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

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

示例

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题

突然有了考试做题的感觉,我觉得首先题目要先审清楚,然后自己尝试用自己已有的知识去解决。
实在做不出来,也别泄气,算法道路一定是曲折的,起码对我来说是这样,大佬除外。

另外,不管做不做出来,都要去学习下示例解法,学习解题思路,从中收获更多。

1. 解法1

我自己尝试着做,这题因为属于简单难度,我用for循环的知识进行了暴力破解,代码以python3为例:

def twoSum(nums, target):

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

其实就是2次循环,最外层的循环,从列表第一个开始遍历,直到最后一个元素,长度就是len(nums)
因为题目中说,单元素不能使用两次,所以内层的循环,就从i 之后也就是i+1开始,直到最后一个元素。

拿到了2个数,就进行相加操作,与target进行比较,如果相等,就返回出这2个元素的下标。

运行一下:

def twoSum(nums, target):

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]


if __name__ == "__main__":
    print(twoSum2([2, 15, 11, 7], 9))

-------------结果----------------------
D:\Programs\Python\Python36\python.exe D:/练习/leecode/two_sum.py
[0, 3]

Process finished with exit code 0

这题虽然我做出来,但是这个解法并不好,如果遇到一个元素很多的列表,并且最后的2个值 之和 等于目标值,那么这种情况下,
数组里的任意2个元素都要匹配比较一次。

时间复杂度就为:O(N^2)。
空间复杂度还好,因为没去去开辟额外的空间去计算,所以是:O(1)。

关于复杂度的分析,后面单独写一篇介绍。

2. 解法2

上面的解法缺点就是在最坏的时候,数组里的任意2个元素都要匹配比较一次,那么就要来解决这个问题。

换个思路来想,遍历列表的中的元素x,如果列表中存在 target-x,那么这2个数的下标就是最终我们要的结果。
官方的建议解法用了哈希表,对于key-value这样的存储形式,x跟它的下标是对应的,这样一来,找到target-x的时间复杂度就变成了O(1)。

所以新的解法就是:

def twoSum2(nums, target):
    hashtable = dict()
    for i, num in enumerate(nums):
        if target - num in hashtable:
            return [hashtable[target - num], i]
        hashtable[nums[i]] = i
    return []

这里使用python,可以创建一个空字典。再利用python中的enumerate()函数,遍历出列表里的元素和下标。
在每一次的遍历中,就可以用目标值 target —— 当前元素 num,判断这个值 在不在字典里。
这里用到的是Python 字典 in 操作符,用于判断键是否存在于字典中。

如果在的话,那就返回 字典里的 元素以及,下标。
因为刚开始循环的的时候,字典里没数据,所以当每次循环后,我们要把这次循环的元素跟它的下标 分别 作为 key和value放到字典里去。

可以加个打印看下 字典的操作过程:

def twoSum2(nums, target):
    hashtable = dict()
    for i, num in enumerate(nums):
        if target - num in hashtable:
            return [hashtable[target - num], i]
        hashtable[nums[i]] = i
        print(hashtable)
    return []


if __name__ == "__main__":
    print(twoSum2([4, 15, 3, 7, 2], 9))

=============================结果==============================
D:\Programs\Python\Python36\python.exe D:/练习/leecode/two_sum.py
{4: 0}
{4: 0, 15: 1}
{4: 0, 15: 1, 3: 2}
{4: 0, 15: 1, 3: 2, 7: 3}
[3, 4]

Process finished with exit code 0

最终,分析解法2的复杂度:

时间复杂度—— O(N),N 是列表中的元素数量。对于每一个元素 x,我们可以 O(1) 地寻找 target - x。
空间复杂度—— O(N),其中 N 是数组中的元素数量。主要是哈希表的开销,在空间上的消耗。

其实也不能说解法1就是最烂的,因为算法没有最好的算法,只有最适合的算法。
随着需求在空间和时间的取舍的不同,具体决定使用哪种算法也是不同的。

二、小结

在这个简单算法里,学习和回顾到的知识点:

  • 哈希表的优点
  • python的enumerate()函数的运用
  • Python 字典 in 操作符,用于判断键是否存在于字典中
发表评论

相关文章