python练习题---给定一个整数数组 nums 和一个目标值 target

系统 144 0

收集一些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


            
          

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


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

发表我的评论
最新评论 总共0条评论