首页 > 代码库 > [Leetcode] Two Sum @Python
[Leetcode] Two Sum @Python
首先作这个题，最直接的思路是两个for循环，然而所带来的缺陷是时间复杂度太高O(n2)。所以要转变思路：如何能一次遍历就解决问题？
因为是两个数相加来得到一个既定的数（target），那就有一个思路是：能不能两头相加，然后通过头指针和尾指针来回向中间靠拢来实现？
答案是可以的。分两步走：
- 排序
- 设置头、尾两指针，实现一次遍历。
注意事项：
- 找到两个数后需要返回两个数的位置，所以需要先备份原序列，使用备份序列进行排序和查找操作，然后查看备份序列找到的数在原序列的位置。
- 在查看备份序列找到的数在原序列位置时，因为要找两个数，所以第一个数要从前遍历，第二个数要从后遍历。否则会出现如下错误：num = {0,2,4,0} target = 0
语法细节：
- 对于序列的复制，可以采用num[:]实现，效果是生成了一个与num相同的新的序列
- 对于Python一个类中方法的定义，第一个参数为self,
- 一个Python模块自己测试，使用 if __name__ == ‘__main__‘:
- 对于一个类Solution，创建实例方式:solution = Solution()
代码实现：
class Solution: # @return a tuple, (index1, index2) def twoSum(self, num, target): numtosort = num[:] numtosort.sort() i = 0 j = self.search(numtosort,target) while(i < j): if(numtosort[i] + numtosort[j] == target): be = self.before_search(num,numtosort,i) af = self.after_search(num,numtosort,j) if be < af: return (be,af) else: return (af,be) elif(numtosort[i] + numtosort[j] < target): i = i + 1 else: j = j - 1 def search(self,numtosort,target): for i in range(0,len(numtosort)): if numtosort[len(numtosort)-i-1] <= target: if i == 0: return len(numtosort)-1 else: return len(numtosort)-i def before_search(self,num,numtosort,number): for i in range(0,len(num)): if(num[i] == numtosort[number]): return i+1 def after_search(self,num,numtosort,number): for i in range(0,len(num)): if(num[len(num)-i-1] == numtosort[number]): return len(num)-iif __name__ == ‘__main__‘: num = [-3,4,3,90] target = 0 solution = Solution() print solution.twoSum(num,target)
[Leetcode] Two Sum @Python
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。