我是靠谱客的博主 勤恳路人,最近开发中收集的这篇文章主要介绍Leetcode——1.两数之和(python)1.两数之和,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

1.两数之和

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

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

示例:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

这个题看起来简单,但是需要注意一些方面:

1. 找到符合条件的两个数,返回的是一个列表,列表里是这两个数对应的下标。

2. 注意不能是自己加自己。

程序代码1:

直接用两个for循环暴力破解。

class Solution:
    def twoSum(self, nums, target):
        nums_length = len(nums)
        for i in range(nums_length):
            for j in range(nums_length):
                if i != j:
                    if nums[i] + nums[j] == target:
                        return [i,j]

nums = [2, 7, 11, 15]
target = 9
s = Solution()
print(s.twoSum(nums, target))

但是很容易发现两个for循环进行运算的话,其中进行了很多重复的计算,比如2+7,7+2,2+11,11+2 .... 所以要解决不必要的重复计算。

程序代码2:

同样也是两个for循环,遍历每一个列表元素,查找看是否存在与target - nums[i] 相同的目标元素。这里把重复的计算去掉,来提高运行速度。

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

nums = [2, 7, 11, 15]
target = 9
s = Solution()
print(s.twoSum(nums, target))

程序代码3:

进行优化,用一次for循环来实现。

class Solution:
    def twoSum(self, nums, target):
        nums_length = len(nums)
        for i in range(nums_length):
            one_num = nums[i]
            the_other_num = target - one_num
            if the_other_num in nums:
                j = nums.index(the_other_num)
                if i != j:
                    return [i,j]

nums = [2, 7, 11, 15]
target = 9
s = Solution()
print(s.twoSum(nums, target))

程序代码4:

对上面一个for循环再进行优化,这里模拟哈希表进行运算。

class Solution:
    def twoSum(self, nums, target):
        nums_length = len(nums)
        hashmap = {nums[i]: i for  i in range(nums_length)}
        for i in range(nums_length):
            one_num = nums[i]
            the_other_num = target - one_num
            if the_other_num in hashmap and i != hashmap[the_other_num]:
                    return [i,hashmap[the_other_num]]

nums = [2, 7, 11, 15]
target = 9
s = Solution()
print(s.twoSum(nums, target))

 

最后

以上就是勤恳路人为你收集整理的Leetcode——1.两数之和(python)1.两数之和的全部内容,希望文章能够帮你解决Leetcode——1.两数之和(python)1.两数之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(47)

评论列表共有 0 条评论

立即
投稿
返回
顶部