欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:33:39
...

收集一些python的练习题,在追求应用的同时千万不要忘了基础的东西,我会不定期的总结一些我做过的小题目,大家一起进步!

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

解题一
这道题拿过来首先很容易想到暴力解决没错我第一步也是这么干的,很容易想到两个循环进行判断,这个代码很容易看的懂,也很容易理解,不做多解释,但是这样运行的时间和所占内存都是非常大的。很不好的一种方法。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = []
        len_nums = len(nums)
        for i in range(len_nums):
            for j in range(i+1,len_nums):
                num = nums[i] + nums[j]
                if num == target:
                    result.append(i)
                    result.append(j)
                    break
        return result

解题二

利用哈希字典查找,通过枚举将数值对应关系放入字典中,然后判断目标值和每一个值得差值在不在字典中。时间复杂度为O(n) 空间复杂度为O(n)


def tow_sum_with_dict(nums, target):
    _dict = {}
    for i, m in enumerate(nums):
        _dict[m] = i
    for i, m in enumerate(nums):
        j = _dict.get(target - m)
        if j is not None and i != j:
            return [i, j]

if __name__ == '__main__':
    nums = [2, 7, 11, 15]
    target = 9
    a = tow_sum_with_dict(nums,target)

解题三
一遍字典模拟Hash,其实这个是接着上一个来的,对上一种方法的优化
当判断不符合条件时往字典中添加键值。这样能够节省内存的消耗。

def tow_sum_with_dict2(nums, target):
        _dict = {}
        for i, m in enumerate(nums):
            if _dict.get(target - m) is not None:
                return [i, _dict.get(target - m)]
            _dict[m] = i

有什么建议或不懂的欢迎评论方留言,我们一起沟通交流!

推荐阅读