twoSum | leetcode学习之路

1）题目链接：https://leetcode.com/problems/two-sum/ 2）题目翻译：传入一个nums列表，一个整型target，在nums中寻找两个数加起来等于target，并返回这两个数的index。 3）知识点学习 定义一个Solution类，类中定义一个twoSum函数。 nums:List[int] 是python3中的新特性， 直接加冒号注释传入参数的类型。 ->代表返回值的类型

4）编程

class Solution(object): def twoSum(self,nums,target): result = [] for i in range(len(nums)): for j in range(i+1,len(nums)): if (nums[i] + nums[j] == target): result.append(i) result.append(j) return result a = Solution() print (a.twoSum([2,3,6],9))

5）问题总结 在此过程中遇到了是否应该往twoSum中传入self的问题：

TypeError: unbound method a() must be called with A instance as first argument (got nothing instead)

错误原因：函数a()非静态方法，故需实例化然后才能使用：

class Solution: def hello(self): print("It's a soluton") obj = Solution() obj.hello()

或者将a()改为静态方法即可，如下：

class Solution: @staticmethod def hello(): print ("It's a solution") Solution.hello()

6）优化 改变思维 将列表里的数作为key 将index作为value 这样可以保证列表里重复的数只存一次 且寻找这个数不需要遍历这个列表 利用字典key-value 的 hashtable性质 将时间复杂度优化到O(n)

class Solution(object): def twoSum(self,nums,target): size = 0 d1 = {} d2 = {} while size < len(nums): if not nums[size] in d1: d1[nums[size]] = size else: d2[nums[size]] = size if (target - nums[size] in d1) and target - nums[size] != nums[size]: result = [d1[target - nums[size]],d1[nums[size]]] return result elif target - nums[size] in d2: result = [d2[target - nums[size]],d1[nums[size]]] return result size = size + 1 a = Solution() print (a.twoSum([2,9,6,3,9,2],9))

还可以先判断有无答案，再放入dictonary，但是速度大大下降

class Solution(object): def twoSum(self,nums,target): size = 0 d = {} while size < len(nums): if (target - nums[size] in nums) \ and (nums.index(target - nums[size]) != size): #遍历列表使得时间复杂度变成了O(n2) d[nums[size]] = size result = [d[nums[size]],nums.index(target - nums[size])] return result size = size + 1