LeetCode 第一题 (Python)

大家好，我是讯享网，很高兴认识大家。

题目内容

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例: 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

今天做了leetcode的第一道题，题意很简单，就是给定一组数和一个目标值，从这组数中找到两个数加起来等于目标值，输出目标值的下标。

刚刚见到这道题，没有多想（缺点），直接使用暴力遍历，两个循环嵌套，逐个进行相加运算，复杂度是O(n2)

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

讯享网

讯享网target == nums[i] + nums[j]

所以，可以考虑将这一步放入上一级循环，代码变为

class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in range(len(nums)): a = target - nums[i] for j in range(i+1,len(nums)): if a == nums[j]: return [i, j]

这样就可以提交了，但是速度依然十分缓慢，要提高速度就要使用新的算法，查找大神的解法，找了一篇博客，[LeetCode]题解（python）：001-Two-Sum
这篇博客提供了三种解法
第一种就是暴力解法，速度慢
第二种是将这组数先排序，再利用“夹逼定理”来处理，排序算法还未接触，所以暂时不考虑。
第三种是使用python中的dict，和C++中的map功能一样，建立一个字典，字典的关键字是这组数的值，字典的内容是这组数的值，我们查找target-nums(size)和nums(size)是否在字典中来找到答案。
博客中给出了第三种方法的代码，实现如下：

讯享网class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d={} size=0 while size < len(nums): if not nums[size] in d: d[nums[size]] = size if target-nums[size] in d: if d[target-nums[size]] < size: return [d[target-nums[size]],d[nums[size]]] size = size + 1

代码提交之后，显示了运行错误，错误的实例是

输入：[3,3] 6 输出：[0,0] 预期：[0,1]

dict中的关键字不能重复，当给定的数中有重复数字时，则会导致这一步

讯享网if not nums[size] in d: d[nums[size]] = size

构建字典不成功，无法正确的进行计算。
所以，对上述代码进行改进。
因为出错的地方是构建字典这一步，我们每一次都把nums(size)写入字典，再进行target-nums(size)的寻找。
所以，可以想到，我们可以先进行target-nums(size)的寻找，如果找到直接输出，如果未找到，再写入字典，这样就避免了重复元素对构建字典的影响。
改进后的代码是

class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d={} size=0 while size < len(nums): if target-nums[size] in d: if d[target-nums[size]] < size: return [d[target-nums[size]],size] else: d[nums[size]] = size size = size + 1

LeetCode 第一题 (Python)

相关推荐