python(leetcode)-1.两数之和

2019-02-17 01:53:59来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

示例:

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

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

 看到这道题,不难理解,就是找出两个值的和等于特定值的下标。

笔者没有太多的想法,用python暴力法先实现一遍

上代码(未通过-超出时间限制)

 1 class Solution:
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         result=[]
 9         for i in range(len(nums)):
10             for j in range( len(nums)):
11                 if(nums[i]+nums[j]==target and i!=j):
12                     result.append(i)
13                     result.append(j)
14                     break
15         aset=set(result)        #利用set无重复性消除重复添加
16         alist=list(aset)
17 
18         return alist
19 
20 if __name__=="__main__":
21     s=Solution()
22     nums=[3,2,4]
23     print(s.twoSum(nums,6))

分析原因:代码两层for循环,时间复杂度为O(n^2),所以遇到数据量大的情况耗时较久。

优化:上代码(通过-6800ms)击败20%

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result=[]
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):   #第i个和第i个之后的数值进行求和对比
                if(nums[i]+nums[j]==target ): #取消了i和j的对比
                    result.append(i)
                    result.append(j)
                    break

        return result

if __name__=="__main__":
    s=Solution()
    nums=[3,2,4]
    print(s.twoSum(nums,6))

解释一下:

       两层for循环每一个和其他元素进行求和的过程中会出现,相同的数操作两遍的情况(比如i为下标3的数,j为下标6的数)当i和j的值互换(i=6,j=3)又求和进行操作,所以第二层循环再第i+1个开始,避免重复操作。这样理论可以提高50%的效率。但是时间复杂度依旧为O(n^2)。所以比较耗时。

之后怎么也想不到更好的方法,

所以借鉴评论区的大佬代码(通过-48ms)击败89%

 1 class Solution:
 2 
 3     def twoSum(self,nums,target):
 4         """
 5         :param nums:
 6         :param target:
 7         :return:
 8         """
 9         sort=sorted(range(len(nums)),key=lambda x:nums[x])
10         i=0
11         j=len(nums)-1
12         alist=[]
13         while(nums[sort[i]]+nums[sort[j]]!=target):  
14             if(nums[sort[i]]+nums[sort[j]]>target):  #当最大的元素和最小的元素相加大于目标值
15                 j-=1                                 #最大元素前移一个位置
16             else:                                    #小于目标值时
17                 i+=1                                 #最小元素后移一个位置
18         alist.append(sort[i])
19         alist.append(sort[j])
20         return alist
21 
22 if __name__=="__main__":
23     s=Solution()
24     nums= [2, 1, 3, 8, 4]
25     print(s.twoSum(nums, 6))

说下设计思想:(首尾递归查找)

首先第一部的排序有点技巧性,因为我们需要排序后才能首位递进查找,但是又需要返回排序前的下标。

所以根据list的值排序并且保存的是list的下标。这样就可以找到排序前的下标。

后面的代码比较简单,当和大于target时,最后一个位置向前移,当和小于target时,第一个位置向后移,

时间复杂度分析:

sorted()的复杂度为O(nlogn)

while()的复杂度为O(n)

所以复杂度为O(nlogn)  比之前的O(n^2)快了很多

 

然后在介绍一个更快的方法 先上代码(通过44ms)超过99%

 1 class Solution:
 2     def twoSum(self,nums,target):
 3         """
 4         :param nums:
 5         :param target:
 6         :return:
 7         """
 8         dit={}
 9         for index,num in enumerate(nums): #遍历值和下标
10             sub=target-num                
11             if(sub in dit):
12                 return [dit[sub],index]   #返回字典中的下标和index
13             dit[num]=index                #将num和index插入dit中
14         return None
15 if __name__=="__main__":
16     s=Solution()
17     nums= [2, 1, 3, 8, 4]
18     print(s.twoSum(nums, 4))

解释下设计思想:

利用字典可以存放key和value。根据与target的差值查找是否出现在字典中,如果有则返回下标,无则将index和num放入字典中并且遍历下一个,直到结束。

该方法for循环N次 减法操作1次,字典查询是否存在最优情况下是1次,字典赋值语句1次

总的复杂度为O(n) 所以该方法特别快

 


原文链接:https://www.cnblogs.com/bob-jianfeng/p/10386417.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Python练手例子(7)

下一篇:清除过期日志的py脚本